What to analyze?

두 알고리즘 A, B가 주어졌을 때, 둘 중 어느 알고리즘이 더 좋다고 판단할 수 있을까요? 단순히 두 알고리즘을 모두 implement하여 실행하는 것으로 비교할 수도 있지만, 이는 얼마나 길게, 얼마나 많이 실행할 지, input data의 size는 어떻게 정해줄 지에 따라 그 결과가 천차만별일 것입니다. 따라서 어떤 것이 좋은 알고리즘인지 분석하기 위해서는 더 general한 방법이 필요합니다.

두 알고리즘을 비교하는 데 가장 주요한 방법은 수학적인 접근입니다. 예를 들어, 두 알고리즘에 모두 size가 $N$인 input이 주어졌을 때 A는 $N$에 비례한 시간이 걸리고, B는 $N^2$에 비례한 시간이 걸린다고 했을 때, 시간 효율성의 측면에서 A가 더 좋은 알고리즘이라고 평가할 수 있습니다.

---

Asymptotic notation

앞선 예시에서 두 알고리즘의 수행 시간을 각각 input size $N$을 활용하여 나타내주었으며, 대체로 알고리즘의 수행시간은 input size가 증가함에 따라 같이 증가하는 경향을 보입니다. 여기서 우리가 관심있게 봐야 하는 부분은 $N$이 매우 큰 수인 영역입니다. $N$이 작은 경우는 수행시간이 아무리 길어도 수 ms 이내에 끝날 확률이 높아 분석하는 의미가 없으며, 주로 우리가 해결해야 하는 문제는 매우 큰 input size를 필요로 하기 때문입니다.

이를 간단한 식으로 표현하기 위해서 Asymptotic notation을 주로 사용합니다. Asymptotic notation은 $o(n)$, $O(n)$, $\Theta(n)$, $\Omega(n)$, $\omega(n)$의 총 5가지의 symbol을 사용합니다. 각각이 의미하는 것을 수식으로 표현하면 다음과 같습니다.

5개의 symbol 중에서 가장 strong한 조건을 가지고 있는 것은 $\Theta$(big-Theta) notation입니다. $f(n)=\Theta(g(n))$은 $f(n)$과 $g(n)$이 충분히 큰 n에 대해서 같은 rate로 증가한다는 것을 의미하며, 이는 두 수식의 leading term이 동일하다는 것을 의미하기도 합니다. 또한 동일한 $\Theta(f(n))$을 가진 수식은 동일한 class에 속한다고 이야기하기도 하며, class 사이의 관계를 weak ordering(또는 asymptotic larger / smaller)으로 나타내 $\Theta(n) \lt \Theta(n^2)$와 같이 표현하기도 합니다.

또 주로 사용하는 symbol은 $O$(big-O) notation입니다. 이는 어떤 수식의 upper bound를 표현하기 위해 사용하는 경우가 많으며, 어떤 알고리즘이 다른 알고리즘보다 더 efficient하다는 것을 보이기 위해 주로 사용합니다.

---

Example of asymptotic analysis

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는 모두 $\Theta(1)$에 해당합니다. 따라서 위의 code 또한 $\Theta(1)$의 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가 $\Theta(1)$임을 알 수 있습니다. for loop에 의해 해당 statement가 n번 반복하기 때문에 n에 비례한 수행시간이 나타나므로 총 time complexity는 $\Theta(n)$이 됩니다.

두 번째 for loop은 두 개의 for loop으로 구성되어 있는 것을 볼 수 있습니다. 앞선 예시를 통해 안쪽의 for loop의 time complexity가 $\Theta(n)$임을 확인했으므로, 이를 n번 반복하는 code이기 때문에 총 time complexity는 $\Theta(n \times n) = \Theta(n^2)$이 됩니다.

마지막 for loop은 안쪽의 statement의 time complexity가 $O(m)$입니다. big-Theta notation이 되지 않은 이유는 best case의 경우 constant time에 수행될 수 있어 경우에 따라 수행시간이 달라지고 그 maximum이 m에 비례하기 때문입니다. 이 경우 다시 for loop에 의해 n회 반복되므로 총 time complexity는 $O(nm)$이 됩니다.

// 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가 $\Theta(1)$이고 후자의 경우 앞서 살펴본 바와 같이 $\Theta(n)$이 될 것입니다. 따라서 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가 $\Theta(1)$의 time complexity를 가지므로 전체 time complexity는 $\Theta(n)$임을 알 수 있습니다.

---

Reference
"Data Structure & Algorithm Analysis in C++", 4th ed, Pearson, M. A. Weiss