CH1-2 알고리즘의 성능분석 방법(2)
순차탐색 알고리즘을 보며 시간복잡도가 무엇인지 알아보자.
순차탐색 알고리즘의 시간복잡도를 평가하기 위한, 중심이 되는 연산자는 무엇인가?
== 이다.
알고리즘에서 중심이 되는 연산자를 찾는 건 어렵지만… 한가지 팁이 있다. 다른 연산자에 의존적이지 않은 독립적인 연산자, 그 중에서도 다른 연산자들이 가장 많이 의존하는 연산자를 찾으면 된다.
중심적인 연산자는 본인의 결과가 다른 연산자들의 연산횟수를 결정한다.
시간복잡도를 계산할때는 해당 알고리즘의 최악의 경우를 고려해야한다.
순차 탐색 같은 경우는, 최선의 경우는 연산횟수가 항상 1이지만, 최악의 경우는 배열의 인덱스수, n이다. 알고리즘을 평가하는데는 최악의 경우를 고려하는게 유의미함.
그렇다면 평균적인 경우는?(Average case)
문제는 무엇이 평균인가? 결정하기 매우 어렵다.
평균적인 경우를 어떻게 구현하는가? 평균적인 경우임을 어떻게 증명하는가? 평균적인 경우의 환경을 어떻게 구성하는가?(평균적인 환경의 평균적인 경우..?)
하지만 최악의 경우는 결정할 수 있다.
순차탐색 (최악의 경우) 시간복잡도는 n이다.
$T(n) = n$