선형 및 이진 탐색

데이터 크기와 탐색 시간에 따른 시간 복잡도의 그래프

선형 알고리즘 linear algorithm은 데이터쌍(인덱스와 이에 매칭되는 값)을 이용해 선형적으로 요소를 탐색하는 방법이다. 실행 시간은 요소 개수 증가에 정비례하여 증가하므로 시간 복잡도는 O(n)이다. 선형 탐색은 결과를 얻기 위해 배열의 모든 요소를 살펴봐야 하므로 느리다.
반면 이진 탐색 binary search은 요소가 많을수록 요소 하나당 탐색에 걸리는 시간이 짧아지는 알고리즘이다. 이진 탐색은 배열이 정렬된 상태에서 중간 요소를 기준으로 탐색의 범위를 1/2씩 줄여나간다. 이때 정렬된 데이터 수를 n, 비교 횟수를 m이라고 하면 다음 식이 성립한다.

n x (1/2)ᵐ = 1
n = 2ᵐ
m = log₂n

(이때 log는 지수의 역연산이다. y= aˣ이면, x = log𝖺y)

이러한 관계에 따라 이진 탐색의 시간 복잡도는 O(logn)이 된다.