자료구조와 알고리즘 (2)

알고리즘의 성능 분석

- 수행시간 측정방법

가장 단순하지만 가장 확실한 방법은 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터상에서 실행시킨 다음, 그 수행시간을 측정하는 것이다. C언어에서 수행시간을 측정하는 방법에는 다음과 같이 2가지의 방법이 있다.

 

[방법 1]

#include <time.h>

start = clock();
...
stop = clock();

double duration = (double)(stop - start) / CLOCKS_PER_SEC;

clock() 함수는 호출 프로세스에 의하여 사용된 CPU 시간을 계산한다. clock() 함수는 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환한다. 따라서 초단위의 시간을 측정하기 위하여 (stop - start)값을 CLOCKS_PER_SEC로 나누어 주면 된다.

 

[방법 2]

#include <time.h>

start = time(NULL);
...
stop = time(NULL);

double duration = (double)difftime(stop, start);

time() 함수는 초 단위로 측정된 시간을 반환한다. time(NULL) 형태로 호출하면 현재 시간이 넘어온다. 두 가지 시간을 difftime()으로 보내면 차이가 초단위로 반환된다.

 

- 빅오 표기법

f(n) = 5 -> O(1)
f(n) = 2n + 1 -> O(n)
f(n) = 3n² + 100 -> O(n²)
f(n) = 5·2ⁿ + 10n² + 100 -> O(2ⁿ)

 

빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로써 시간복잡도를 간단하게 표시할 수 있다. 빅오 표기법을 얻는 간단한 방법은 기본연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것이다. 최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용한다. 다만, logn은 없애버리면 안 된다. logn도 차수를 가지고 있기 때문이다.

f(n) = 8n²logn + 5n² + n -> O(n²logn)

 

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ) < O(n!)

여기서 주의할 것은 상수항이나 계수가 굉장히 큰 경우에는 수행시간에 영향을 끼친다는 것이다. 예를 들어 두개의 알고리즘, A와 B가 있다고 하고 이들의 시간 복잡도 함수가 각각 T1(n) = 100n + 100이고 T2(n) = n²라고 하자. 알고리즘 T1을 빅오 표기법으로 표기하면 O(n)이 되고 T2는 O(n²)이 되지만 실제로 다음 표에서 보듯이 알고리즘 T1이 더 효율적이 되는 것은 n > 100인 경우이다. 따라서 n이 작을 때는 상수항이나 각항의 계수도 영향을 끼친다.

n	T1(n) = 100n + 100, O(n)	T2(n) = n², O(n²)
1	200	1
10	1100	100
50	5100	2500
100	10100	10000
1100	110100	1210000

 

n이 증가할 때 시간 복잡도 함수가 얼마나 증가하는지 도표로 살펴보자. 알고리즘이 지수형(2ⁿ)이나 팩토리얼형(n!)의 시간복잡도를 가지면 사실상 사용할 수 없는데 그 이유를 아래 표에서 알 수 있다. 알고리즘이 지수형이나 팩토리얼형의 시간복잡도를 가지고 있는 경우, 입력의 개수가 30을 넘으면 현재의 가장 강력한 슈퍼 컴퓨터를 동작시켜도 우주가 탄생되어 지금까지 흘러온 시간보다 더 많은 수행 시간을 요구할 수도 있다.

시간복잡도	n
	1	2	4	8	16	32
1	1	1	1	1	1	1
logn	0	1	2	3	4	5
n	1	2	4	8	16	32
nlogn	0	2	8	24	64	160
n²	1	4	16	64	256	1024
n³	1	8	64	512	4096	32768
2ⁿ	2	4	16	256	65536	4294967296
n!	1	2	24	40326	20922789888000	26313 X 10³³

 

참고

• C언어로 쉽게 풀어쓴 자료구조 책