글에 들어가기전에, 시간복잡도(Time Complexity) 라는 개념이 나오는데,
이는 알고리즘의 빠르기를 판단하기 위해 알고리즘의 중심이되는 연산의 횟수를 세는것을 이야기한다.
무슨말인지모르겠다면 아래글을 쭉 읽어보면 된다. 그럼 이해가 될것이다. ㅎ,ㅎ
---------------------------------------------------------------------------------
순차탐색(Linear Search)은 말 그대로 순차적으로 자료구조를 탐색을하는것을 이야기한다. 아래 배열을 살펴보자.
이 배열에서 내가 찾고자하는 숫자를 배열의 첫번째 인덱스부터 차례대로 탐색해나가는것이다. 예를들어 내가 찾고자하는숫자가 33이라면, 인덱스 [0] 부터 차례대로 확인해가면서 인덱스를 늘려간다. [0]을 확인했는데 33이 아니므로 [1]로 넘어가고, [1]을 확인했는데 33이 아니므로 [2]로 넘어간다. 이를 계속반복 하면 [5]에서 33을 찾게된다. 이런식으로 원하는 요소를 찾아가는게 순차탐색이다.
그럼 여기서 순차탐색의 시간복잡도는 어떻게 나올까? '12' 를 찾는경우엔 한번의 탐색만을 진행하므로 시간복잡도가 1이다. '17'을 찾는경우엔 다섯번의 탐색을 진행하므로 시간복잡도가 5이다. '7'을 찾는경우엔 여덟번의 탐색을 진행하므로 시간복잡도가 '8'이다. 이렇듯 시간복잡도는 상황에따라 달라지는데, 최상의경우 / 평균적인경우 / 최악의경우 세가지로 나누어 생각한다.
시간복잡도를 표현할때는 T(n) 이라는 표현을 사용하기로 하는데, 이는 n개의 탐색 대상을 탐색할때 걸리는 시간복잡도를 표현한다.
1. 최상의 경우 (Best case)
- 최상의경우는 원하는요소를 가장 빠르게 찾는 경우이다.
따라서 위의경우 Best case는 원하는요소를 한번에 찾는 '1' 이 될것이다.
2. 최악의 경우 (Worst case)
- 최악의경우는 원하는요소를 가장 늦게 찾는 경우이다.
따라서 위의경우 Worst case는 원하는요소를 가장 늦게 찾는 '8' 이 되며, 이는 탐색대상의 수인 n이다.
3. 평균적인 경우 (Average case)
- 평균적인경우는 말그대로 요소를 찾을때 어떤상황에서든 평균적으로 걸리는 경우이다(따라서 최상의경우와 최악의경우도 이에 포함되게된다). 평균적인경우에는 흔히 생각하는것처럼 (n/2) 이겠지만, 추가적으로 생각해야할 사항이있다. 바로 원하는 대상이 없을경우이다. 원하는 대상이 없을때는 탐색대상의 수만큼 n의 탐색을 진행한후 false를 리턴하므로 이경우도 생각해야한다. 임의로 원하는대상이 탐색대상에있을확률을 50% 라고 한다면 평균적인 경우는 아래와같이 계산된다.
그렇다면 알고리즘마다 세가지의경우를 모두 고려해야할까? 그렇지않다. 일단 최상의경우는 고려해야할 대상이 아니다. 어떤 알고리즘이던 best case는 1이기때문이며 비현실적인 경우이기때문이다. 그리고 평균적인경우는 고려하기에 애매하다. 위의경우는 원하는대상이 탐색대상에있을확률을 50%라고 정했지만 세상의 모든 자료들이 50%확률로 탐색대상에 있을것이라 단정지을수없다. 그리고 탐색대상에있다하더라도 n/2라는 수치는 근사치 이기 때문에 '이 알고리즘의 시간복잡도는 n/2'라 표현하기가 뭐하다. 따라서 시간복잡도를 표현할때는 worst case만을 이야기한다.
따라서, 순차탐색(Linear Search)의 시간복잡도(Time Complexity)는 다음과 같다.
