- 다음의 각각의 함수의 최악의 경우의 시간복잡도를 점근적(asymptotic) 표기법으로 나타내면? 이유는?
int fun1(int n, int data[]) {
int sum = 0;
for (int i = 0; i < n; i+=2)
sum += data[i];
return sum;
}A. O(n), for문 안의 sum += data[i]; 문장을 i가 증가함에 따라 계속해서 순회하는 함수인데 최악의 경우에는 n/2번만큼 순회를 해야하기 때문에 시간복잡도를 O(n/2)라고 할 수 있지만 통상적으로는 O(n/2)=O(n)이기 때문에 O(n)이 된다.
int fun2(int m, int A[], int n, int B[], int C[]) {
int i = 0, j = 0, k = 0;
while(i < m && j < n) {
if (A[i] < B[j])
C[k++] = A[i], i++;
else if (A[i] > B[j])
C[k++] = B[j], j++;
else
C[k++] = A[i], i++, j++;
}
while (i < m)
C[k++] = A[i], i++;
while (j < n)
C[k++] = B[j], j++;
return k;
}A. 첫번째 while 문에서 최악의 경우에는 A[i]를 m번 순회하고, B[j]를 n번만큼 순회하기 때문에 시간복잡도는 O(m+n)가 된다. 세번째 while 문에서는 최악의 경우에는 A[i]를 m번 순회하고 네번째 while 문에서 최악의 경우에는 B[j]를 n번 순회하기 때문에 결국에 위 함수에서의 최악의 경우의 시간복잡도는 O(m+n)이 된다.
double fun3( int n ) {
double sum = 0;
for (double i = 1.0; i < n; i *= 1.5)
sum += i;
return sum;
}A. for문 안에서 sum += i;라는 문장을 반복하면서 순회하는 함수인데 i가 1.5배씩 커지므로 실행횟수는 n을 초과하기 전까지 log1.5(n)이 된다. 따라서 최악의 경우의 시간복잡도는 O(log15(n))인데 통상적으로 O(log(n)이라고 한다.
int fun4(int n, int target, int data[] ) {
int count = 0, i = 0, j = n-1;
while (i<j) {
if (data[i] + data[j] == target)
count++, i++, j--;
else if (data[i] + data[j] < target)
i++;
else
j--;
}
return count;
}
A. 최악의 경우는 i와 j가 while문 안에서 계속 순회하다가 마지막에 만나는 경우인데 이 경우에서 실행횟수는 n/2번이 되므로 시간복잡도는 O(n/2)가 되는데 통상적으로 O(n)으로 한다.
int fun5( int n, int K, int data[] ) {
int count = 0;
for (int i=0; i<n; i++) {
int result = binary_search(n, data, K-data[i]); /* 이진검색을 수행한다. */
if (result != -1)
count++;
}
return count;
}A. 이진 검색을 하면 for문을 한번 순회할 때 마다 실행횟수가 절반이 되므로 최악의 경우는 절반씩 계속 나누다가 마지막에 검색을 성공하는 경우이다. 이때 시간복잡도는 O(log2(n))이 되는데 통상적으로 O(log(n))이라 한다.
/* 배열 A와 B에 각각 m개와 n개의 정수가 오름차순으로 정렬되어 저장. 그 외에 어떤 가정도 없음 */
void fun6(int m, int A[], int n, int B[]) {
for (int i=0; i<m; i++) {
for (int j=1; j<n; j*=2) {
if (A[i] <= B[j])
break;
}
}
}A. 위 함수는 m번 반복되면서 j가 2배씩 증가하면서 n을 초과하지 않을때까지 for문을 반복하는 함수인데 우선 안쪽 for문에서는 j가 2배씩 증가함에따라 log2(n)번 반복되므로 시간 복잡도는 O(log(n))이고 바깥쪽 for문에서는 최악의 경우 m번 반복하므로 총 시간복잡도는 O(mlog(n))이 된다.
int fun7(int n). {
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}A. 바깥쪽 for문에서 i가 절반씩 줄어들기 때문에 O(n^2) 반복 횟수는 log2(n)이 되고 안쪽 for문에서는 i번 반복하는데 반복 횟수는 n+n/2+n/4...+1번 반복하게 되는데 n이 계속 커진다고 가정할 때 2n에 근접하게 되므로 총 시간 복잡도는 O(n)이 된다.
