#5. 이진 탐색 알고리즘 시간 복잡도

시간 복잡도를 구하기 위해, 당연하게도 함수를 먼저 구해서 그래프를 그려야 한다.

...
while(first <= last)
{
	center = (first + Last) / 2;
    if(target == ar[center]) return center;
    else ...
}

이 기본 골격에서 핵심 연산은 " == " 연산이다.

이전 순차 탐색 알고리즘에서 봤던 것과 동일하게 다른 연산자, 추가로 if / else 문 의 시행 또한 == 연산자에 의존한다.

 

따라서 == 연산자의 연산 횟수를 기준으로 시간 복잡도를 결정할 수 있다.

 

탐색 대상은 ( n => n/2 => n/4 .... ) 으로 절반씩 줄어들면서 진행된다.

 : 언제까지? 탐색 대상이 1개가 될 때까지

 : 그래서 몇번이냐? 모른다! => 객관적 성능 비교가 불가능하다.

 

해서 이 탐색 대상이 1개가 될 때까지 총 몇번을 시행해야 하는지 정확한 수식을 세울 필요가 있다.

 

이 추론 과정을 통해 T(n) = K + 1 이라는 공식이 성립되었고 이는

이라는 n을 2로 k번 나누는 공식으로 표현할 수 있다. ex) n = 8일 때, k = 3

이를 보기쉽게 다시 정리하면

k = Log2N 으로 정리할 수 있다.

정확하게 표현해서

이다. 티스토리 블로그로 수학 공식을 표현하는 방법을 찾지 못했다....

따라서 T(n) = Log2N + 1 이라고 말할 수 있는데 이 때 + 1은 생략한다.

그래프로 나타내면

이러한 형태를 가진, 아주 사용하기 좋은 알고리즘 그래프를 그릴 수 있다.

 

왜 +1을 생략하는가?

이러한 수식 정립의 목적은 변화 패턴을 알기 위한 것이다.

+1 에 영향받는 정확한 수치를 얻으려고 하는 것이 아니기 때문이다.

 

시간 복잡도의 목적은

n의 값에 따른 T(n) 의 증가/감소의 정도를 판단하기 위함 이다.