프로그램의 시간 복잡도(time complexity)는 프로그램을 실행시켜 완료하는데 걸리는 시간을 의미한다.
어떤 프로그램의 실행 시간을 추정하기 위해서는 모든 기본 명령문의 실행 빈도수(frequency count)를 알아야 한다. 여기서 기본 명령문은 지정문, 조건문, 반복문 속의 제어문 그리고 stop, return 등을 포함한다. 엄밀한 구분은 어렵지만 시간 복잡도의 추정을 목적으로 하기 때문에 프로그램 문맥상 하나의 연산 단위를 하나의 단계로 계산하면 의도한 목적 달성에 충분하다.
시간 복잡도에서는 한 단계로 계산되는 모든 기본 명령문은 실행 시간이 하나의 단위 시간으로 모두 같다는 가정을 하고 있다. 그렇기 때문에 복잡한 연산문을 한 단계로 계산할 때와 a=2와 같은 간단한 지정문을 하나의 실행 단계로 계산할 때의 실행 시간의 차이는 고려하지 않는다.
시간 복잡도를 표기하는 방법 중 big-oh 표기법이 있는데 이는 실행 시간 n을 O(n)으로 표기한다. 일반적으로 양의 두 함수 f와 g에 대한 f(n) = O(g(n))은 함수 f(n)의 시간 복잡도가 O(n)이라는 뜻이다.
<정의> Big-oh(O)
f와 g를 각각 양의 정수를 갖는 함수라 할 때, 만일 어떤 두 양의 상수 a와 b가 존재하고, 모든 n ≥ b에 대하여, f(n) ≤ a*g(n)이면 f(n) = O(g(n))이다.
함수 ex1()의 소스 코드는 다음과 같이 분석할 수 있다.
|
함수 ex1()의 경우 |
실행 빈도수 |
|
void ex1(int n) { |
- |
|
int count = 0; |
1 |
|
int i; |
1 |
|
for (int i = 0; i < n; i++) |
n + 1 |
|
count++; |
n |
|
} |
- |
따라서 함수 ex1()의 프로그램 단계들의 총 실행 빈도수,
즉 실행 시간은 2n+3 이 된다. 그러나 이 보고서에서 실행 시간은 count값으로 하기 때문에 실행 시간은 n 이 된다.
여기서
big-oh 표기법으로 나타내면
f(n) = n, g(n) = n 으로 놓으면
n≥b 인 모든 n에 대하여 n ≤ a*n 인 a와 b를
a = 2, b = 1 로 정할 수 있으므로
함수 ex1()의 시간 복잡도는 O(n) 으로 쓸 수 있다.
함수 ex2()의 소스 코드는 다음과 같이 분석할 수 있다.
|
함수 ex2()의 경우 |
실행 빈도수 |
|
void ex2(int n) { |
- |
|
int count = 0; |
1 |
|
int i; |
1 |
|
for (int i = 0; i < n; i+=2) |
(n / 2) + 1 |
|
count++; |
n / 2 |
|
} |
- |
따라서 함수 ex2()의 실행 시간(count 값)은 n/2 가 된다.
여기서
big-oh 표기법으로 나타내면
f(n) = n/2, g(n) = n 으로 놓으면
n≥b 인 모든 n에 대하여 n/2 ≤ a*n 인 a와 b를
a = 1, b = 1 로 정할 수 있으므로
함수 ex2()의 시간 복잡도는 O(n) 으로 쓸 수 있다.
함수 ex3()의 소스 코드는 다음과 같이 분석할 수 있다.
|
함수 ex3()의 경우 |
실행 빈도수 |
|
void ex3(int n) { |
- |
|
int count = 0; |
1 |
|
int i; |
1 |
|
for (int i = 0; i < n*n; i+=2) |
((n*n) / 2) + 1 |
|
count++; |
((n*n) / 2) |
|
} |
- |
따라서 함수 ex3()의 실행 시간(count 값)은 (n^2)/2 이 된다.
여기서
big-oh 표기법으로 나타내면
f(n) = (n^2)/2, g(n) = n^2 으로 놓으면
n≥b 인 모든 n에 대하여 (n^2)/2 ≤ a*(n^2) 인 a와 b를
a = 1, b = 1 로 정할 수 있으므로
함수 ex3()의 시간 복잡도는 O(n^2) 으로 쓸 수 있다.
함수 ex4()의 소스 코드는 다음과 같이 분석할 수 있다.
|
함수 ex4()의 경우 |
실행 빈도수 |
|
void ex4(int n) { |
- |
|
int count = 0; |
1 |
|
int i, j; |
1 |
|
for (int i = 0; i < n; i++) |
n + 1 |
|
for (int j = 0; j <= i; j++) |
((n * (n+1)) / 2) +1 |
|
count++; |
(n * (n+1)) / 2 |
|
} |
- |
따라서 함수 ex4()의 실행 시간(count 값)은 (n^2)/2+n/2 가 된다.
여기서
big-oh 표기법으로 나타내면
f(n) = (n^2)/2+n/2, g(n) = n^2 으로 놓으면
n≥b 인 모든 n에 대하여 (n^2)/2+n/2 ≤ a*(n^2) 인 a와 b를
a = 1, b = 1 로 정할 수 있으므로
함수 ex4()의 시간 복잡도는 O(n^2) 으로 쓸 수 있다.
함수 ex5()의 소스 코드는 다음과 같이 분석할 수 있다.
|
함수 ex5()의 경우 |
실행 빈도수 |
|
void ex5(int n) { |
- |
|
int count = 0; |
1 |
|
int i, j; |
1 |
|
for (int i = 0; i < n*n; i++) |
n*n + 1 |
|
for (int j = 0; j <= i; j++) |
((n*n * (n*n+1)) / 2)+1 |
|
count++; |
(n*n * (n*n+1)) / 2 |
|
} |
- |
따라서 함수 ex5()의 실행 시간(count 값)은 (n^4)/2+(n^2)/2 가 된다.
여기서
big-oh 표기법으로 나타내면
f(n) = (n^4)/2+(n^2)/2, g(n) = n^4 으로 놓으면
n≥b 인 모든 n에 대하여 (n^4)/2+(n^2)/2 ≤ a*(n^4) 인 a와 b를
a = 1, b = 1 로 정할 수 있으므로
함수 ex5()의 시간 복잡도는 O(n^4) 으로 쓸 수 있다.
다음은 실제 프로그램을 실행시켜 본 결과이다.
ex1()
ex2()
ex3()
ex4()
ex5()
실제 프로그램을 실행시켜 본 결과와 big-oh 표기법으로 나타낸 n의 값에 따른 각 함수의 실행 시간을 비교해 보면 다음과 같다.
함수 ex1()
n | O(n) | count |
1 | 1 | 1 |
2 | 2 | 2 |
4 | 4 | 4 |
8 | 8 | 8 |
16 | 16 | 16 |
32 | 32 | 32 |
64 | 64 | 64 |
함수 ex2()
n | O(n) | count |
1 | 1 | 1 |
2 | 2 | 1 |
4 | 4 | 2 |
8 | 8 | 4 |
16 | 16 | 8 |
32 | 32 | 16 |
64 | 64 | 32 |
함수 ex3()
n | O(n^2) | count |
1 | 1 | 1 |
2 | 4 | 2 |
4 | 16 | 8 |
8 | 64 | 32 |
16 | 256 | 128 |
32 | 1024 | 512 |
64 | 4096 | 2048 |
함수 ex4()
n | O(n^2) | count |
1 | 1 | 1 |
2 | 4 | 3 |
4 | 16 | 10 |
8 | 64 | 36 |
16 | 256 | 136 |
32 | 1024 | 528 |
64 | 4096 | 2080 |
함수 ex5()
n | O(n^4) | count |
1 | 1 | 1 |
2 | 16 | 10 |
4 | 256 | 136 |
8 | 4096 | 2080 |
16 | 65536 | 32896 |
32 | 1048576 | 524800 |
64 | 16777216 | 8390656 |
소스 코드는 다음과 같다
.결론
big-oh 표기법으로 나타낸 실행 시간과 실제 실행 시간을 비교한 결과를 보면 n이 계속적으로 무한히 커질 때 f(n)의 값은 결국 g(n)을 상한으로 점점 가깝게 점근적으로 한정되기 때문에, g(n)을 f(n)의 어림값으로 볼 수 있다는 것을 알 수 있다.
그렇기 때문에 big-oh를 점근식 표기법(asymptotic notation)이라 하는데, 이상의 점근적 복잡도 계산 방법은 다음과 같은 몇 가지 문제점을 포함하고 있다는 것도 알 수 있다.
-복잡한 알고리즘의 분석
-알고리즘에 대한 복잡도의 평균값
-알고리즘간의 미소한 차이 계산 불가
-값이 정확하지 않다
참고1>http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=106956796&qb=YmlnLW9oIGNvdW50&enc=utf8§ion=kin&rank=3&search_sort=0&spq=0
참고2>http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=68494777&qb=YmlnLW9oIOy9lOuTnA==&enc=utf8§ion=kin&rank=6&search_sort=0&spq=0
'메모 > 자료구조' 카테고리의 다른 글
| C 연결리스트 연산 (0) | 2012.03.31 |
|---|---|
| C 미로찾기 (0) | 2012.03.31 |
| 다항식의 자료구조 (0) | 2012.03.31 |
