알고리즘의 수행 시간을 좌우하는 기준은 다양하게 잡을 수 있습니다. 예를 들면 반복문의 반복 횟수, 특정한 행이 수행되는 횟수, 함수의 호출횟수 등이 있죠.
복잡도 분석 예시
| Algorithm A |
Algorithm B |
Algorithm C |
| sum <- n*n; |
for i<-1 to n do
sum <-sum + n; |
for i<-1 to n do
for j<-1 to n do
sum <-sum + 1; |
위 알고리즘의 연산 수는 각각 2번, 2n번, 3n^2+n번입니다. 대표로 1번, n번, n^2번이라고 합니다.
입력값이 커질 수록 상수를 더하거나, 뺴거나, 곱하거나, 나누는 연산은 알고리즘 복잡도에 영향력이 미미하기 때문입니다.
Algorithm C를 살펴봅시다.
# Algorithm C
for i<-1 to n do # 대입(<-): n번
for j<-1 to n do # 대입(<-): n^2번
sum <-sum + 1; # 대입(<-): n^2번, 더하기(+) : n^2번
맨 아래에서 sum에 1을 더하는 더하기 연산을 기준으로 복잡도를 분석하면 전체 알고리즘 복잡도를 n^2으로 정의할 수 있습니다. 그리고 같은 n^2번이 수행되는 다른 대입 연산들을 기준으로 분석해도 동일합니다.
하지만 가장 바깥의 반복문의 대입 연산을 기준으로 분석할 수는 없습니다. n번밖에 수행되지 않기 때문에 아무리 큰 상수를 곱해도 나중에는 나머지 연산들(n^2)의 연산 수를 넘어설 수는 없기 때문입니다.
그래서 3n^2 + n이나 n^2이나 복잡도 분석 측면에서 같다고 보는 것입니다.
몇가지 알고리즘을 더 살펴봅시다.
algorithm(A[], n) {
k = ⌊n/2⌋;
return A[k];
}
연산 수는 총 4번입니다. 나누기 연산, 버림 연산, 대입 연산, 반환할 때의 연산이 들어간 것이죠. n에 관계 없이 상수 시간내에 완료됩니다.
algorithm(A[], n) {
sum ← 0;
for i ← 1 to n
sum← sum+ A[i];
return sum;
}
연산 수는 총 3n+3, 대표로 n번입니다. 3과 +3는 영향력이 미미하기 때문입니다. 함수 실행, sum대입, 반복문 n번, sum대입 n번, sum더하기 n번, 반환의 연산이 들어간 것이죠.
algorithm(A[], n) {
sum ← 0;
for i ← 1 to n
for j ← 1 to n
sum← sum+ A[i]*A[j];
return sum;
}
연산 수는 총 n^2번입니다.
algorithm(A[ ], n) {
sum ← 0;
for i ← 1 to n
for j ← 1 to n {
k ← A[1 ... n]에서 임의로 floor(n/2)개를 뽑을 때 이들 중 최댓값;
sum ← sum + k;
}
return sum;
}
연산 수는 n^3 + 4n^2 + n + 3, 대표로 n^3입니다. 연산 수가 n^2인 연산은 j대입, k대입, sum대입, sum + k입니다. 여기에 추가로 floor(n/2)개를 뽑는 경우와 이것 중 최댓값을 찾는 경우는 두 연산 모두 n^3 / 2 연산이 소요됩니다. 따라서 상수 연산을 무시한 n^3이 총 연산 수가 됩니다.
algorithm(A[], n) {
sum ← 0;
for i ← 1 to n-1
for j ← i+1 to n
sum← sum+ A[i]*A[j];
return sum;
}
n이 7이라면 j가 몇번 반복할까요? 6 + 5 + 4 + 3 + 2 + 1 번 반복합니다. 이것을 n에 대한 식으로 바꾸면 (n-1) + (n-2) + ... + 1이 됩니다. 공식은 n(n-1)/2 이죠. 그래서 연산 수는 총 n(n-1)/2이며 대표로 n^2번입니다.
algorithm(n) {
if (n=1) return 1;
return n * algorithm(n-1);
}
factorial 연산을 하는 알고리즘입니다. 함수 수행은 n번, if (n=1)은 n번, return 1은 1번 일어나며 밑의 return문은 모두 n-1번 일어납니다. 마지막 반환 시 return 1을 하므로 그 밑은 수행하지 않기 때문이죠. 연산 수는 총 n번입니다.
algorithm(A,n) {
tmp ← A[0];
for i←1 to n-1 do
if tmp < A[i] then
tmp ← A[i];
return tmp;
}
배열에 들어있는 원소 중 최댓값을 구하는 알고리즘입니다. 연산 수는 n번입니다.
index algorithm(int n, keytype S[], keytype x) {
index location
location = 1;
while (location <= n && S[location] != x)
location++;
if (location > n) location = 0;
return location;
}
순차탐색 알고리즘입니다. 배열 S에서 index 1부터 index n까지 순차적으로 x를 찾아 위치를 반환합니다. 연산 수는 n번입니다.
int algorithm(int n){
index i;
int f[] = new int[n+1];
f[0] = 0;
f[1] = 1;
if (n > 1) {
for (i=2; i<=n; i++)
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
n위치의 피보나치 수를 구하는 알고리즘입니다. 연산 수는 n번입니다.
void algorithm(int n, keytype S[]) {
index i, j;
for (i = 1; i <= n-1; i++)
for (j = i+1; j <= n; j++)
if ( S[j] < S[i] ) exchange S[i] and S[j];
}
배열 S를 교환 정렬하는 알고리즘입니다. 수행시간을 좌우하는 기준은 안쪽 for문에 있는 연산 전체이며 총 연산 수는 n(n-1)/2, 대표로 n^2입니다.
index algorithm(int n, keytype S[], keytype x) {
index location, low, high, mid;
low = 1;
high = n;
location = 0;
while ( low <= high && location == 0 ) {
mid = ⌊(low + high) / 2⌋;
if (x == S[mid]) location = mid;
else if (x < S[mid]) high = mid - 1;
else low = mid + 1;
}
return location;
}
배열 S에서 x를 찾는 이분 탐색 알고리즘입니다. 수행시간을 좌우하는 기준은 while문에 있는 연산 전체이며 이 알고리즘은 반복 수행마다 n을 반씩 나누어 계산하기 때문에 최악의 경우인 데이터가 1개 남는 경우를 고려하면 총 연산 수는 (1/2)^k * n = 1이 되며 양변에 2^k를 곱하면 n = 2^k, 다시 양변에 log를 취하면 logn = k가 됩니다.