빅 오(Big O)

빅 오 분석  : 입력 값의 개수에 따라 알고리즘이 수행되는 데 걸리는 시간을 바탕으로 알고리즘의 효율성을 판단하는 실행 시간 분석법

빅 오 분석법에서는 입력 값의 개수(크기)를 n개라고 가정한다.

빅 오 실행시간 분석은 다음과 같이 이루어진다.

1. 입력 값을 확인하고 n을 어떤 값으로 놓아야 할지 결정.

2. 알고리즘에서 수행해야 할 연산 횟수를 n으로 이루어진 식으로 표현

3. 차수가 제일 높은 항 남기기.

4. 모든 상수 인수를 없앤다.

성능이 좋은 것부터 나쁜 것까지 순서대로 알고리즘 종류를 나열해보면 다음과 같다.

O(lg n) > O(n) > O(n lg n) > O(n^c) > O(c^n) > O(n!)

(lg는 밑이 2인 로그함수를 의미)

왼쪽이 성능이 가장 좋은것이고 오른쪽으로 갈 수록 나빠지는 것이다.

예시를 통해 좀 더 살펴보자.

아래의 코드는 삽입정렬에 대한 코드이다.

void insertion_sort(int* list, int n) {
	int key, i, j;
	for (i = 1; i < n; i++) {
		key = list[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (key >= list[j]) break;
			else {
				list[j + 1] = list[j];
			}
		}
		list[j + 1] = key;
	}
}

이와같이 삽입정렬이 있을 때 입력값의 크기가 n이 되므로 배열의 크기가 n이라고 할 수 있다.

느닷없이 삽입정렬에 대한 예시를 가져온 이유는 최선, 평균, 최악 케이스의 복잡도에 대한 얘기를 하기 위함이다.

알고리즘의 시간 복잡도를 분석할 때는 최선, 평균, 최악케이스에 대해 생각해보아야 하며

상황에 맞게 사용할 줄 알아야한다.

위의 삽입정렬에서 최악의 경우는 {5, 4, 3, 2, 1}과 같이 역순으로 오는 경우이며 

이 떄 시간 복잡도는 O(n^2) 이 된다.

최선의 경우는 {1, 2, 3, 4, 5}와 같이 오는 경우이며 이동 없이 1번의 비교만 이루어지므로 

시간 복잡도는 O(n)이다.