#7. 순차 탐색 vs 이진 탐색

순차 탐색의 최악의 경우 시간 복잡도는

T(n) = n 으로 나타내고 이는 빅-오 표기법으로 O(n) 으로 나타낸다.

 

이진 탐색의 최악의 경우 시간 복잡도는

T(n) = Log2N + 1 로 나타내고 이는 빅-오 표기법으로 O(LogN) 으로 나타낸다.

 

둘을 비교하기 위해선 n에 증가량에 따른 연산 횟수를 살펴봐야 하는데

단순 계산만 보더라도

순차 탐색의 연산횟수보다 이진 탐색의 연산 횟수가 극단적으로 적다는 것을 알 수 있다

 

특히 이진 탐색의 연산 횟수는 n의 값이 증가함에 따라 그 상승폭이 점점 더 줄어드는 모습으로

이는 사용하기 좋은, 매우 뛰어난 알고리즘이다 라고 결론 내릴 수 있다.