CH1-2 알고리즘의 성능분석 방법(6)
이진탐색 알고리즘의 (최악의 경우의)시간복잡도는?
핵심 연산자는 비교 연산자이다. 다른 연산들은 모두 == 에 의존하고 있음.
== 가 빨리 true를 반환하면 연산횟수도 줄어들기 때문…
최악의 경우, 즉 타겟이 없을때, $n, {n\over 2}, {n \over 4}...1$ 개의 원소가 남을때까지 총 $k$번 타겟을 찾고, 원소가 1개일때 한번 더 탐색을 진행하므로 총 $k+1$번 탐색을 진행한다.
이 $k$를 $n$에 대한 식으로 만들어보자.
$$ n\times({1\over 2})^k = 1 $$
$k$는 $n$을 계속 반으로 나눠서 1이 될때까지의 횟수이다.
위의 식을 다시 $k$에 대한 $n$의 식으로 바꾸면?
양번에 로그를 취하는 것이 핵심임.
$T(n) = k+1$이었으므로, $T(n) = log_2n+1$인데, $n$이 매우 커지면 1정도는 의미가 없으므로, $T(n) = log_2n$이다.
알고리즘의 성능분석 방법(7)
상수를 제거하는 것이 어떻게 합리적인 것으로 인식될까? 이는 시간복잡도 함수를 어떤 관점에서 평가할까에 따라 달라짐. 시간복잡도는 최악의 경우를 따질때 평가됨. 이때 중요한건 $n$이 급격히 증가할때 이 알고리즘이 어떤 효율성을 보이는가를 따지는 것임… 따라서 $n$이 급격하게 커지면, 작은 상수는 의미가 없어진다..