[자료구조] 이진 탐색 vs 선형 탐색

이진 탐색을 소개할 때 '효율적'으로 값을 찾는 방법이라는 표현을 썼다.그렇다면 실제로 이진 탐색이 선형 탐색에 비해 얼마나 더 효율적이 된 것일까? 이를 측정하는 방법을 알아보자.

 

시간 재기

가장 기본적인 방법은 시간을 재보는 것이다.

x축은 배열의 크기, y축은 걸린 시간 (단위 macro sec)

 

1) 걸리는 시간의 스케일 자체가 다르다. 선형 탐색은 10단위로 올라가는데 이진 탐색의 경우은 0.05 단위로 그 증감이 표현된다.

 

2) 배열의 개수가 증가함에x 따라 걸리는 시간의 증가 추세가 이진 탐색이 훨씬 완만하다. 

 

즉 이진 탐색이 더 빠르고 배열의 개수가 늘어남에 따라 증가하는 시간의 추세 또한 더 완만하다.

 

 

reference:

https://justinpombrio.net/2020/03/01/linear-vs-binary-search.html

Justin Pombrio