[ 알고리즘 ] 이진 탐색이란? 시간의 복잡도 계산하기

이진 탐색이란? 시간의 복잡도 계산하기

 

배열을 대상으로 이진 탐색 알고리즘을 적용하기 위해서는 배열에 저장된 데이터가 정렬되어 있어야 합니다. 

즉, 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능합니다. 

 

---

그럼 이해를 위해 그림을 먼저 보겠습니다. 

다음과 같이 정렬된 배열이 있습니다. 배열의 요소 중 3은 어느 인덱스에 있는지 알고 싶다고 가정하겠습니다. 

 

1. 배열의 가운데를 찾기 위해 인덱스의 시작과 끝을 더해 2로 나눕니다. 

2. 인덱스 3에 있는 요소와 목표값이 같은지 비교합니다.

3. 아니네요. 인덱스 3에 있는 요소(7)는 목표값(3)보다 큽니다.

---

4. 범위를 0~2로 하여 다시 인덱스의 시작과 끝을 더해 2로 나눕니다.

 

5. 인덱스 1에 있는 요소와 목표값이 같은지 비교합니다.

6. 같네요. 

 

여기서 찾지 못했더라도 목표값을 찾을 때까지 탐색 범위를 줄여가며 비교를 반복하면 됩니다. 

---

 

이제 이진 탐색 알고리즘의 코드 구현을 보겠습니다. 

 

---

최악의 경우 이진 탐색 알고리즘의 시간 복잡도를 계산해보겠습니다. 

 

이진 탐색 알고리즘을 일부를 보면서 어떤 연산이 핵심인지 알아봅시다. 

 

 

 

 

탐색 대상의 중앙을 찾고, 중앙에 저장된 요소가 목표값이라면... 아니라면...

즉, == 연산을 연산횟수를 대표하는 연산으로 볼 수 있겠네요. 

 

 

 

 

---

그럼 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)를 구성해봅시다. 

 

1. 데이터가 n개일 때 1회 비교연산 진행

2. 데이터를 반으로 줄여서 n/2일 때 1회 비교연산 진행

3. 데이터를 반으로 줄여서 n/4일 때 1회 비교연산 진행

4. 데이터를 반으로 줄여서 n/8일 때 1회 비교연산 진행

...

?. 데이터를 반으로 줄여서 1개일 때 1회 비교연산 진행

 

데이터 수를 모르니 탐색 대상이 1개일 때까지 얼마나 비교연산이 진행되어야 할지 알 수 없습니다. 

그래서 데이터수가 n을 대상으로 다음과 같이 일반화할 수 있습니다. 

 

- n이 1이 되기까지 2로 나눈 횟수 k회 -> 비교연산 k회

- 데이터가 1개 남았을 때, 마지막으로 비교연산 1회

 

 

최악의 경우에 대한 시간 복잡도 함수는 아래와 같이 됩니다. 

T(n) = k + 1

 

그럼 여기서 연산횟수를 가리키는 k를 구해봅시다. 

k에 관한 식으로 정리하면 됩니다. 

 

정리된 최종 수식의 양 변에 밑이 2인 로그를 취합니다. 

 

최종적으로 다음과 같은 식이 됩니다. 

 

앞에서 최악의 경우에 대한 시간 복잡도 함수는 k + 1이라고 했는데  여기서는 +1를 왜 안 했는지 의아해할 수 있습니다.

사실 +1를 중요하지 않습니다. 중요한 것은 데이터의 수 n이 증가하면서 비교연산의 횟수가 로그적으로 증가한다는 점입니다.

즉, n에 대한 식 T(n)을 구성하는 목적은 데이터 수 증가에 따른 연산횟수의 변화 정도를 판단하는 것으므로 +1은 중요하지 않습니다.  

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------