[CS] 선형 검색 알고리즘과 이진 검색 알고리즘을 알아보자

선형 검색 알고리즘

전 게시글의 Search에서 언급했었던 선형 검색 알고리즘은 배열의 처음부터 끝까지 순차적으로 탐색해 찾는 값을 찾을 때까지 반복한다.

따라서 배열의 맨 마지막에 있거나 아예 없는 경우, 또는 배열이 길다면 들여다 볼 것들이 그만큼 많아지므로 시간 복잡도가 같이 높아진다.

 

그래서 최악의 경우 배열 모두를 돌아야 하기 때문에 시간 복잡도는 O(n) 이 되며 배열의 크기에 비례해 시간이 증가한다.

 

이러한 이유로 선형 검색 알고리즘이 큰 배열에서는 효율적이지 않을 수 있다.

그래서 정렬된 배열이나 더 빠른 검색을 위해 이진 검색 알고리즘을 사용한다.

---

이진 검색 알고리즘

정렬된 배열에서 특정 값을 찾는데 사용되는 효율적인 검색 알고리즘이다.

명시한 것처럼 '정렬된 배열'에서만 사용이 가능하다. 이처럼 어떤 알고리즘은 특정 배열에서만 사용할 수 있다.

 

arr = [2, 10, 3, 14, 20, 5] 일 때 5를 찾고 싶다.

이 때 정렬을 하면 [2, 3, 5, 10, 14, 20]이 되고 5를 더 빨리 찾을 수 있다. 

 

하지만 정렬된 배열이라고 모든 작업이 빠른 것은 아니다.

예를 들어 7을 넣고 싶을 때, 정렬된 배열이 아닐 경우에는 공간만 있으면 되니 맨 끝에 넣을 수 있다.

반면 정렬된 배열은 7보다 작은 값과 7보다 큰 값 사이에 넣어야 하므로,

비교 + 삽입한 후 데이터들을 오른쪽으로 옮기는 과정이 필요해 삽입 자체는 오래 걸린다.

 

그래서 아무튼 이진 검색 알고리즘은 정렬이 되어야 사용할 수 있다는 것이다.

 

이진은 0과 1을 의미하는 게 아니라 반으로 쪼개는 것을 의미한다.

선형 검색처럼 인덱스 0부터 순차적으로 주르륵 진행하는 것이 아니라, 가운데부터 시작해서 가운데를 기준으로 목표보다 큰지 작은지를 나눈다.

예를 들어 1부터 10까지 있는 배열이 있을 때 9의 위치를 찾아야 한다면 선형 검색은 1부터 9까지 검색하겠지만 이진 검색은 5부터 잘라 들어가고 오른쪽을 기준으로 또 반을 나눠 자르고 자르고... 이런 식으로 3번이면 찾을 수 있다.

 

이런 이진 검색은 배열의 길이가 길어져도 스텝이 크게 늘지 않는다.

매 스텝마다 절반을 없애고 시작하기 때문에 이 점에서는 무척 효율적이다.

---

Big O

알고리즘의 시간 복잡도를 나타내는데 사용되는 표기법

알고리즘이 실행되는 동안 소요되는 시간이나 연산 횟수를 나타낸다.

이를 통해 알고리즘의 성능을 비교하고 분석할 수 있다.

 

O는 Order of의 약자다.

 

• O(1) : 상수 시간 복잡도. 입력 크기에 관계 없이 항상 일정한 실행 시간을 갖는다.
  • arr = [1, 2, ... 10]인 배열에서 arr[0]을 찾는 데에 시간 복잡도 O(1)을 표현한다.
• O(log n) : 로그 시간 복잡도. 입력 크기의 로그에 비례하는 실행 시간을 갖는다. 이진 검색 같이 분할 정복 알고리즘이 여기에 해당된다.
• O(n) : 선형 시간 복잡도. 입력 크기에 직선적으로 비례하는 실행 시간을 갖는다. 배열의 모든 요소를 둘러보는 선형 검색이 이에 해당된다.
• O(n log n) : 선형 로그 시간 복잡도. 입력 크기에 대한 로그와 선형의 곱으로 비례하는 실행 시간을 갖는다. 퀵 정렬과 병합 정렬 등 정렬 알고리즘이 이에 해당된다.
  • 퀵 정렬은 피벗을 기준으로 배열을 분할하고 병합 정렬은 반으로 나누어 정렬하는데 이 부분은 일단 넘어가자.
• O(n^2) : 이차 시간 복잡도. 입력 크기의 제곱에 비례하는 실행 시간을 갖는다. 이중 루프를 사용하는 버블 정렬이나 선택 정렬이 이에 해당한다.
  • 버블 정렬은 배열에서 아이템 2개를 선정해 크면 오른쪽, 작으면 왼쪽으로 계속 이동 시키는 정렬 알고리즘이다.
  • 선택 정렬은 아이템을 다 돌면서 위치를 저장하고, 가장 작은 아이템을 왼쪽으로 이동 시킨다. 
• O(2^n) : 지수 시간 복잡도. 입력 크기에 대한 2의 거듭제곱에 비례하는 실행 시간을 갖는다. 완전탐색과 재귀적인 알고리즘이 이에 해당한다.

---