이진탐색 알고리즘의 시간 복잡도 그리고 빅-오 표기법

'윤성우의 열혈 자료구조'의 Ch.1 을 보면서 요약한 내용입니다.

 

알고리즘의 시간복잡도 (Time Complexity)는 최악의 경우를 기준으로 계산한다.

 

[EX] 이진탐색 알고리즘의 시간복잡도 계산해보기

 

n개의 데이터에 대해 이진탐색을 진행할 때, 최악의 경우는 데이터가 한 개 남을 때 까지 찾는 경우이다.

연산 횟수를 표현하면 다음과 같다.

• n이 1이 될 때까지 2로 나눈 횟수 : k
• 데이터가 한 개 남았을 때 마지막으로 비교연산 1회 진행

시간 복잡도 계산해보기

$ T(n) = k + 1 $

 

$k$ 구하기

n 이 1이 될 때까지 2로 나눈 횟수가 k 라면 식으로 다음과 같이 표현할 수 있다.

 

$ n \times (\frac{1}{2})^{k} = 1 $

 

$ n \times 2^{-k} = 1 $

 

$ n = 2^{k} $

 

이 식에 양변에밑이 2인 로그를 취하면

$ \log _{2} n = k $

 

따라서 시간 복잡도는 다음과 같이 쓸 수 있다.

$ T(n) = \log _{2} n $

 

사라진 $ +1 $은 데이터의 개수 n이 증가함에 따라 증가하는 연산횟수가 아니므로 중요하지 않다. 따라서 생략해도 된다.

 

이진탐색 소스코드

#include <stdio.h>

int BSearch(int arr[], int len, int target)
{
	int first = 0;
	int last = len - 1;
	int mid;

	while(first <= last)
	{
		mid = (first + last) / 2;

		if(target == arr[mid])
			return mid;
		else
		{
			if (target < arr[mid])
				last = mid - 1;
			else
				first = mid + 1;
		}
	}
	return -1;
}

int main(void)
{
	int arr[] = {1, 3, 5, 7, 9};
	int idx;

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == -1)
		printf("Search Failed. No Value");
	else
		printf("Target stored index : %d\n", idx);

	return (0);
}

 

빅-오 표기법 (Big-Oh Notation)

$ O(n) $

시간복잡도 함수 $T(n)$에서 가장 영향력이 큰 부분만을 따지는 표기법

 

데이터의 증가에 따른 연산횟수의 증가 "패턴"을 보기 때문에, 의미 없는 항을 생략해도 무방하다.

단순하게 빅-오 구하기

• T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.
•        ▶     $ O(n^{m})$
  
  
  대표적인 빅-오
  • $ O(1) $
    - 상수형 빅-오
    
    
  • $ O(\log n) $
    - 데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 알고리즘
    - 이상적인 알고리즘
    - 로그의 밑이 무엇인지는 별로 중요하지 않음
    
    
  • $ O(n) $
    - 선형 빅-오
    
    
  • $ O(n\log n) $
    - 선형 로그형 빅-오
    - 데이터 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가한다.
    - 많은 알고리즘이 이에 해당함
    
    
  • $ O(n^{2}) $
    - 중첩된 반복문에 해당
    - 데이터 수가 많은 연산에서는 사용하기 부적절
    
    
  • $ O(n^{3}) $
    - 삼중 반복문
    
    
  • $ O(2^{n}) $
    - 지수형 빅-오
    - 사용하기에 매우 부적절