두 알고리즘 A, B가 주어졌을 때, 둘 중 어느 알고리즘이 더 좋다고 판단할 수 있을까요? 단순히 두 알고리즘을 모두 implement하여 실행하는 것으로 비교할 수도 있지만, 이는 얼마나 길게, 얼마나 많이 실행할 지, input data의 size는 어떻게 정해줄 지에 따라 그 결과가 천차만별일 것입니다. 따라서 어떤 것이 좋은 알고리즘인지 분석하기 위해서는 더 general한 방법이 필요합니다.
두 알고리즘을 비교하는 데 가장 주요한 방법은 수학적인 접근입니다. 예를 들어, 두 알고리즘에 모두 size가 인 input이 주어졌을 때 A는 에 비례한 시간이 걸리고, B는 에 비례한 시간이 걸린다고 했을 때, 시간 효율성의 측면에서 A가 더 좋은 알고리즘이라고 평가할 수 있습니다.
앞선 예시에서 두 알고리즘의 수행 시간을 각각 input size 을 활용하여 나타내주었으며, 대체로 알고리즘의 수행시간은 input size가 증가함에 따라 같이 증가하는 경향을 보입니다. 여기서 우리가 관심있게 봐야 하는 부분은 이 매우 큰 수인 영역입니다. 이 작은 경우는 수행시간이 아무리 길어도 수 ms 이내에 끝날 확률이 높아 분석하는 의미가 없으며, 주로 우리가 해결해야 하는 문제는 매우 큰 input size를 필요로 하기 때문입니다.
이를 간단한 식으로 표현하기 위해서 Asymptotic notation을 주로 사용합니다. Asymptotic notation은 , , , , 의 총 5가지의 symbol을 사용합니다. 각각이 의미하는 것을 수식으로 표현하면 다음과 같습니다.
5개의 symbol 중에서 가장 strong한 조건을 가지고 있는 것은 (big-Theta) notation입니다. 은 과 이 충분히 큰 n에 대해서 같은 rate로 증가한다는 것을 의미하며, 이는 두 수식의 leading term이 동일하다는 것을 의미하기도 합니다. 또한 동일한 을 가진 수식은 동일한 class에 속한다고 이야기하기도 하며, class 사이의 관계를 weak ordering(또는 asymptotic larger / smaller)으로 나타내 와 같이 표현하기도 합니다.
또 주로 사용하는 symbol은 (big-O) notation입니다. 이는 어떤 수식의 upper bound를 표현하기 위해 사용하는 경우가 많으며, 어떤 알고리즘이 다른 알고리즘보다 더 efficient하다는 것을 보이기 위해 주로 사용합니다.
asymptotic analysis의 적용을 보여주기 위해 몇 가지 code를 살펴보겠습니다.
// code 1 : swap variables a and b
int tmp = a;
a = b;
b = tmp;
위의 code는 3개의 assignment operation으로 이루어져 있습니다. 일반적으로 integer, logical, bitwise, relational operation이나 memory allocation / deallocation 등은 일정 cycle 내에 수행될 수 있는 operation이고, time complexity는 모두 에 해당합니다. 따라서 위의 code 또한 의 time complexity를 가지는 것을 알 수 있습니다.
// code 2 : loops
int sum_1 = 0;
for (int i = 0; i < n; ++i) {
sum_1 += i; // Theta(1)
}
int sum_b = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
sum_2 += 1; // Theta(1)
}
}
for (int i = 0; i < n; ++i) {
// search through an array of size m
// O(m) algorithm
}
code 2의 첫 번째 for loop을 보면, loop 내의 statement의 time complexity가 임을 알 수 있습니다. for loop에 의해 해당 statement가 n
번 반복하기 때문에 n에 비례한 수행시간이 나타나므로 총 time complexity는 이 됩니다.
두 번째 for loop은 두 개의 for loop으로 구성되어 있는 것을 볼 수 있습니다. 앞선 예시를 통해 안쪽의 for loop의 time complexity가 임을 확인했으므로, 이를 n
번 반복하는 code이기 때문에 총 time complexity는 이 됩니다.
마지막 for loop은 안쪽의 statement의 time complexity가 입니다. big-Theta notation이 되지 않은 이유는 best case의 경우 constant time에 수행될 수 있어 경우에 따라 수행시간이 달라지고 그 maximum이 m
에 비례하기 때문입니다. 이 경우 다시 for loop에 의해 n
회 반복되므로 총 time complexity는 이 됩니다.
// code 3 : control statements
void func(int arg, int n) {
if (arg == 0) return;
for (int i = 0; i < n; ++i) {
// Theta(1) statement
}
}
다음으로 control statement에 대해 보겠습니다. 위의 code 3에 해당하는 function을 보면 arg
의 값이 0인 경우 true path를 따라 return하며, 그렇지 않은 경우 false path를 따라 for loop을 수행하게 됩니다. 전자의 경우 time complexity가 이고 후자의 경우 앞서 살펴본 바와 같이 이 될 것입니다. 따라서 control statement의 경우 경우에 따라 time complexity가 변화하게 됩니다.
// case 4 : recursive function
int factorial(int n) {
if (n <= 1) return 1;
else return n * factorial(n - 1);
}
마지막으로 recursive function의 경우를 보겠습니다. recursive function은 함수 자기 자신을 다시 호출하게 되는데, 앞의 for loop과 비슷하게 함수를 호출한 횟수만큼 안의 statement를 수행하게 됩니다. code 4의 예시는 함수를 n
회 만큼 호출하는 경우이며, 내부의 statement가 의 time complexity를 가지므로 전체 time complexity는 임을 알 수 있습니다.
Reference
"Data Structure & Algorithm Analysis in C++", 4th ed, Pearson, M. A. Weiss