https://youtu.be/-bm0-k7UeV8?si=cuHxR9QIKvfeizLI
주니온 교수님의 강의 정리본.

Compleixty analysis

알고리즘의 복잡도 분석을 complexity analysis라고 한다.

알고리즘의 시간 복잡도라는 것은 입력 크기 $n$에 따른 단위 연산의 수행 횟수 변화를 함수로 나타낸 것을 의미한다.

예를 들어 특정 알고리즘에 대한 연산 수행 횟수 $T(n)$을 다음과 같은 함수로 표기하는 방법이다.

우리는 주로 점근적 표기법(Asymptotic Notation)을 사용하여 알고리즘의 시간 복잡도를 표기한다.

점근적 표기법은 시간 복잡도 함수를 대표적인 복잡도 함수 집합의 원소로 표현하는 방법이다.

예를 들어,

이런 점근적 표기법의 종류에는 $O, \Omega, \Theta$가 있다.
빅오($O$)는 알고리즘의 상한선, upper bound를 의미하는 함수이고 이는 worst case를 의미한다. 오메가($\Omega$)는 하한, lower bound이자 best case, 쎄타($\Theta$)는 차수, order를 표기하는 함수이다. 쎄타 표기법은 average case이다. 또한 쎄타 표기법은 다음을 따른다.

반복문의 경우

void func(int n) {
	for (int i = 1; i <= n; i++) {
    	print("Hellow World\n");
    }
}

이런 반복문이 있다면, 총 $n$번 반복하기 때문에 $T(n) = n$으로 표기할 수 있다. 이중 반복문의 경우,

void func(int n) {
	for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= n; j++)
	    	print("Hellow World\n");
    }
}

위 경우에는 $i, j$에 대한 반복문이 이중으로 돌면서 $n^2$번 반복하게 되므로 $T(n) = n^2$으로 표기할 수 있다.

입력 크기에 따른 실행 횟수의 변화가 다양한 경우

void func(int n) {
	for (int i=1; i<=n; i*=2) {
    	printf("test");
    }
    for (int i=n; i>=1; i/=2) {
    	printf("test2");
    }
}

위와 같이 반복문이 2개이고 입력 크기에 따른 실행 횟수가 각 반복문마다 다른 경우도 존재한다. 우선 2를 곱해나가며 반복하는 for문에 대해서는 $1, 2, 4, 8, \cdots, n$까지 반복하므로 반복횟수는 $\log_2 n$라 할 수 있다. 그 다음 2를 나눠가며 반복하는 for문에 대해서는 $n, n/2, n/4, \cdots, 1$까지 반복한다. 이 경우에도 반복횟수는 $\log_2 n$라 할 수 있다. 최종적으로

으로 표기할 수 있다.

입력 크기의 변수가 여러개인 경우

void func(int n, int m) {
	for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j *= 2)
	    	print("Hellow World\n");
    }
}

이렇게 입력 변수가 $n, m$ 2개인 경우에는 어떻게 $T(n)$을 구할까? 가장 먼저 $i$에 대해 반복하는 for문의 경우에는 $n$번 반복하고, $j$에 대해 반복하는 for문은 $\log_2 m$번 반복하게 된다. 이중 반복문이기 때문에,

으로 표기할 수 있다.

재귀함수의 시간 복잡도

재귀함수는 함수가 자기자신을 반복 호출하는 경우로 재귀함수의 시간 복잡도를 구하는 것은 위와 같이 간단하지 않다. 그래서 마스터 정리(Master Theorem)을 사용하게 되는데, 간단한 팩토리얼이나 병합 정렬(merge sort)의 경우에는 다음과 같다.

어려운 경우는 쉬트라센 행렬 곱셈이나 카라츠바 알고리즘과 같은 경우에는 $T(n)$이 팩토리얼의 연산 횟수만큼 간단하게 표현되지 않는다. 이를 위해 마스터 정리를 사용하는데,

Master Theorem

마스터 정리(master theorem)은 어떤 알고리즘의 시간 복잡도 함수 $T(n)$이 다음과 같은 형태일 때,

(여기서 $a,b,c,k$는 상수이고 $a,c > 0$, $b \geq2$, $k \geq0$ 이다.) 이 함수의 $T(n)$은 다음과 같은 점근적 표기법으로 나타낼 수 있다.

여기서 상수들의 의미는 $k$는 반복문이 몇 번 도는지를 의미하고, $a$는 재귀호출을 몇 번 하는지, $b$는 재귀 호출할 때마다 문제의 크기를 얼마나 나누는지를 의미한다.

쉬트라센 행렬 곱셈(Strassen's Algorithm)

쉬트라센 행렬 곱셈의 알고리즘은 7번 재귀호출(곱셈의 횟수)하고, 재귀호출 할 때마다 $n\times n$ 크기의 정방행렬을 $n/2 \times n/2$의 크기로 나눈다. 그렇기에 문제의 크기를 $n$에서 $n/2$로 나눈다고 할 수 있으므로 $a=7$와 $b=2$이다. 또한 더하거나 배는 연산의 횟수는 18번이고 이를 $(n/2)^2$번 반복하기 때문에 $T(n)$은 다음과 같다.

위에서 정의한 마스터 정리를 사용하면,

에 해당하기 때문에, $T(n)$은

이다. 즉, $T(n) \in \Theta(n^{2.81})$이 된다.

큰 정수의 곱셈(Karatsuba's Algorithm)

카라츠바 알고리즘의 경우 $T(n)$은 다음과 같다.

최종적으로 $a=3,\; b=2,\; k=1$임을 알 수 있다. 마스터 정리를 사용하면, $3 > 2^1$이므로 마찬가지로 case 3에 해당한다.