알고리즘의 성능을 평가하는 빅오 표기법

 

컴퓨터의 일은 크게 두 가지로 나눌 수 있다. 데이터를 저장하는 일과 연산하는 일이다. 이때, 어떻게 하면 데이터를 적은 메모리에 저장할 수 있을까 고민하는 것이 자료 구조적인 부분이라면, 어떻게 하면 문제를 더 빠르고 정확하게 해결할 수 있을까 고민하는 것이 알고리즘적인 부분이다. 

시간 복잡도

시간 복잡도	사용 예
O(1)	배열에서 원소 접근(random access) 스택 자료구조에서 삽입(push)과 삭제(pop) 큐에서 삽입(enqueue)과 삭제(dequeue) 해시 테이블에서 원소 접근
O(logN)	이진검색(binary search)
O(N)	배열에서 검색, 최솟값, 최댓값 찾기 연결리스트에서 순회, 최솟값, 최댓값 찾기 계수정렬(버킷정렬)
O(NlogN)	병합정렬 퀵 정렬(평균 시간 복잡도) 힙 정렬
O(N^2)	버블정렬(bubble sort) 선택정렬(selection sort) 삽입정렬(insertion sort)
O(2^n)	피보나치 수열
O(N)	팩토리얼

시간 복잡도는 말 그대로 얼마나 빠르게 결과를 출력할 수 있을까에 대한 고민이다. 이때 시간 복잡도를 어떤 기준으로 측정하는 것이 가장 정확할까?  만약 시간 복잡도를 초 단위로 측정한다면, 같은 프로그램이라도 집에 있는 컴퓨터에서 돌아가는 것과 슈퍼컴퓨터에서 돌아가는 시간은 차이가 클 것이다. 따라서 시간 복잡도는 초 단위로 평가하지 않고, 얼마나 많은 연산을 거쳐야 문제를 해결할 수 있는가로 판단한다. 즉, 시간 복잡도는 연산의 횟수로 평가된다. 

시간 복잡도 표기법 (빅오, 빅오메가, 빅세타)

시간 복잡도를 판단하는 표기법으로는 빅오 표기법, 빅세타 표기법, 빅오메가 표기법 등이 있다.

• Big-O(빅오 표기법): 시간의 상한을 표기한 방법으로, 특정 알고리즘의 최악의 경우 시간 복잡도를 나타낸다.
• Big-Ω(빅오메가 표기법): 시간의 하한을 표기한 방법으로, 특정 알고리즘의 최선의 경우 시간 복잡도를 나타낸다.
• Big-Θ(빅세타 표기법): 시간의 상한과 하한을 동시에 표기한 방법으로, 특정 알고리즘의 평균의 경우 시간 복잡도를 나타낸다. 

최선, 최악, 평균

알고리즘의 효율성을 평가할 때는 3가지의 경우로 나누어서 평가한다. 

• 최선의 경우(Best Case): 알고리즘의 수행시간이 가장 적게 걸리는 경우
• 최악의 경우(Worst Case): 알고리즘의 수행 시간이 가장 오래 걸리는 경우
• 평균적인 경우(Average Case): 알고리즘의 모든 입력을 고려한 후, 입력이 발생하는 확률을 고려해 평균을 구함 

빅오 표기법은 주로 최악의 경우 성능을 평가할 때 사용한다. 즉, 프로그램이 최악의 성능을 보일 때 그 성능이 더 나빠질 수 없는 한계를 나타낸다. 반면, 빅오메가 표기법은 최상의 경우 성능을 평가한다. 즉, 가장 좋을 때 이 정도의 성능을 보장하며, 더 나은 성능은 기대할 수 없다는 의미이다. 하지만 일반적으로 우리는 최악의 경우를 평가하는 빅오 표기법을 많이 사용한다.

빅오 표기법 

시간 복잡도는 주로 O(1), O(log n), O(n), O(n^2) 등의 형태로 나타나는데, O(1)은 가장 좋은 성능을 나타내며, O(2^n)으로 갈수록 성능이 떨어진다.

 

                                   O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)

 

출처:&nbsp;https://blog.kakaocdn.net/dn/cowrIz/btq2Xjqi63N/w8xOGEkHDkBv4PaTfxKKf0/img.png

 

O(N)

• 배열에서 검색, 최솟값, 최댓값 찾기
• 연결리스트에서 순회, 최솟값, 최댓값 찾기
• 계수정렬(버킷정렬)

이 함수는 반복문을 사용해 데이터를 처리하는 방법이다. 만약 데이터의 개수가 100개라면 100번 반복해야 하고, 1000개라면 1000번 반복해야 한다. 이 경우, 데이터의 개수에 따라 연산의 횟수가 선형적으로 증가하기 때문에 O(n)의 시간 복잡도를 갖는다. 

int dosomething(int N) {
	int total = 0;

	for (int i = 1; i <= N; i++)
		total += i;
	return total; 
}

 

O(1)

• 배열에서 원소 접근(random access)
• 스택 자료구조에서 삽입과 삭제 (push & pop)
• 큐에서 삽입과 삭제 (enque & deque)
• 해시 테이블에서 원소 접근

int dosomthing(int N) {
	int total = 0;
	total = (N * (N + 1)) / 2;
	return total; 
}

 

이 함수는 등차수열의 공식을 이용하여 데이터를 처리한다. 이 경우, 데이터의 개수가 100개든 1000개든 단 3번의 연산만으로 문제를 해결할 수 있다.

• N+1을 한다.
• 1번의 값에 N을 곱한다. 
•  2로 나눈다. 

따라서 O(1)의 시간 복잡도를 갖는다. O(1)은 데이터의 크기에 상관없이 항상 일정한 연산을 보장하는 시간 복잡도이다.   

O(N^2)

• 버블정렬(bubble sort)
• 선택정렬(selection sort)
• 삽입정렬(insertion sort)

int dosomething(int N) {
	int total = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			total += i;
		}
	}
	return total; 
}

 

이 함수는 N=2면 4번 돌아야하고 N = 10이면  100번 돌아야하고, N =100이면 10000번 돌아야한다.결국 데이터의 수가 많아질수록 연산의 수가 지수의 수만큼 수식상승한다. 따라서 알고리즘의 성능이 매우 좋지 않다고 할 수 있다. 

O(NM)

N과 M의 크기가 같지 않을 수도 있기 때문에 O(N^2)이 아닌 O(NM)이 된다. 

int doSomething(int N, int M)
{
	int total = 0;
    
    for(int i=0; i<=N; i++)
    	for(int j=0; j<=M; j++)
        	total += (i+j);
            
	return total; 
}

O(logN)

• 이진검색

int dosomething(int N) {
int total = 0;

for (int i = N; i > 0; i /= 2) {
total += i;
}
return total; 
}

 

O(logN) 의 경우는 O(N^2) 과 반대로 연산을 하면 할수록 데이터의 양이 줄어드는 연산이다. 

이진 검색은 정렬된 배열에서 값을 찾는 방법으로, 배열의 중간 값을 기준으로 검색 범위를 반으로 줄여가며 탐색한다. 따라서 O(log n)의 시간 복잡도를 가진다. 로그 시간 복잡도는 데이터의 양이 많아질수록 매우 효율적이다. 

 

예를 들어서 N=10이라고 한다면 for문을 돌 떄마다 2로 반토막이 나니까 N=5, N=3,, N=1 로 점점 작아진다. 

처음에는 연산의 수가 많아보이더라도 나중에는 연산의 횟수가 많아질수록 효율이 아주 좋아진다. 

점근적 표기법 (asymptotic notation)

알고리즘의 실행 시간을 측정하고자 할 때, 두 부분으로 나누어 볼 수 있다. 첫 번쨰는 입력값의 크기에 따른 알고리즘의 실행 시간이다. 즉, 배열의 크기가 커지면 선형 검색(차례대로 탐색)과 이진 검색(왼쪽과 오른쪽 반씩 쪼개서 탐색)의 최대 추측 횟수가 함께 증가한다. 두 번쨰는 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아보는 것인데 이것을 성장률이라고 부른다.성장률을 측정할 때 프로그램을 쉽게 유지할 수 있도록 최고 차항만 남겨서 불필요한 부분은 버리고 가장 중요한 부분만 추려내서 함수를 간소화한다.  

 

예제 코드

int dosomething(int N) {
	int total[5] = { 0 };

	for (int i = 1; i < 5; i++) {
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++)
				total[i] += (i + j + k);
		for (int i = 0; i < N; i++)
		{
			printf("total[%d] = %d/n", i, total[i]);
		}
	}
}

 

예제에서 이중 for문은 5번을 돌고 (i=5) N만큼을 한번 더 도니까  O(5N^2+N) 으로 표현할 수 있다. 

그런데 점근적 표기법에서는 필수적인 부분에만 집중을 한다고 했다. 즉 가장 영향을 많이 미치는 요소에만 집중을 하는 것이다. 그러니까 군더더기 요소들은 과감히 뗴어버리고 O(5N^2+N) 에서 최고 차항만 표기를 하게 된다. 그래서 점진적 표기법에서는 시간 복잡도가  O(5N^2+N) 이 아니라 O(N^2) 으로 표현하게 되는 것이다. 최고 차항을 찾아내는 기준은 데이터가 커질 수록 연산 양이 가장 커지는 차항이다. 

#표준 표기법
O(5N^2+N)

#점근적 표기법
O(N^2)