순차 탐색 알고리즘과 이진 탐색 알고리즘의 비교

순차 탐색 알고리즘의 T(n) 함수:     

이진 탐색 알고리즘의 T(n) 함수:      

                                           →                 

                   →                

※  의 알고리즘을  의 알고리즘으로 개선시키는 것은 약간의 개선이 아닌, 혁신적인 성능의 개선으로 간주된다.

# 비교를 위한 실험의 원칙

- 최악의 경우를 대상으로 비교하는 것이 목적이니 탐색의 실패를 유도한다.

- 탐색의 실패가 결정되기까지 몇 번의 비교연산이 진행되는지를 센다.

- 데이터의 수는 500, 5000, 50000 일 때를 기준으로 각각 실험을 진행한다.

 인 순차 탐색 알고리즘의 경우, 실험을 통하지 않아도 비교연산의 횟수가 500, 5000, 50000 임을 알 수 있다. 선형 빅-오이기 때문에!

두 알고리즘의 비교연산횟수 비교

n	순차 탐색 연산횟수	이진 탐색 연산횟수
500	500	9
5,000	5,000	13
50,000	50,000	16

위의 표에 정리된 결과는  의 알고리즘과  의 알고리즘의 연산횟수에 얼마나 큰 차이가 있는지를 보여준다.