In this post, 03 Algorithm lecture is introuduced.

CLRS chater 3 ~ 4.2 의 내용을 다룬다.

3. Asymptotic notatioin

3.2 $\theta, O, o$ - notation

• $\theta (g(n)) = {f(n) : \exists \ c_1, c_2, n_0 \ s.t \ \forall n\geq n_0, \ 0\leq c_1g(n)\leq f(n)\leq c_2g(n) }$
• $O(g(n)) = {f(n) : \exists \ c, n_0 \ s.t \ \forall n\geq n_0, \ 0\leq f(n)\leq cg(n) }$

• $o(g(n)) = {f(n) : \forall c>0, \ \exists \ n_0 \ s.t \ \forall n\geq n_0, \ 0\leq f(n)<cg(n) }$

  $\iff \lim_{n \to \infty} \frac{f(n)}{g(n)}=0$

4. Divide-and-Conquer

4.1 (3rd edition) The maximum-subarray problem

(시간나면 보기)

4.1 (4th edition) Matrix Multiplication

$n \times n$ Matrix Multiplication을 naive 하게 계산하는 pseudo code는 아래와 같다. 행렬 C에 행렬 곱 AB의 결과를 더해 C=C+AB 꼴로 저장한다. 행렬 곱을 계산하려면 C를 0행렬로 초기화하여 전달하면 된다.

MATRIX-MULTIPLY(A, B, C, n)
1 for i = 1 to n
2 	for j = 1 to n
3 		for k = 1 to n // (AB)_ij 계산
4 			c_ij = c_ij + a_ik * b_kj

위 알고리즘의 경우 Running Time 은 $\theta(n^3)$ 이다.

이제 간단한 Divide-and-Conquer 알고리즘을 사용해 행렬곱을 계산하는 알고리즘을 알아보자.

Divide 단계에서는 $n \times n$ Matrix A, B, C 를 각각 다음과 같이 $n/2 \times n/2$ Matrix 4개로 나눈다.

그러면 행렬 곱셈을 다음과 같이 쓸 수 있다.

MATRIX-MULTIPLY-RECURSIVE(A, B, C, n)
1 if n == 1
2		// base case
3		c_11 = c_11 + a_11 * b_11
4		return
5 // divide
6 partition A, B, C into n/2*n/2 submatrices
7 // conquer
8 Matrix-Multiply-RECURSIVE(A_11, B_11, C_11, n/2)
9 Matrix-Multiply-RECURSIVE(A_11, B_12, C_12, n/2)
10Matrix-Multiply-RECURSIVE(A_21, B_11, C_21, n/2)
11Matrix-Multiply-RECURSIVE(A_21, B_12, C_22, n/2)
12Matrix-Multiply-RECURSIVE(A_12, B_21, C_11, n/2)
13Matrix-Multiply-RECURSIVE(A_12, B_22, C_12, n/2)
14Matrix-Multiply-RECURSIVE(A_22, B_21, C_21, n/2)
15Matrix-Multiply-RECURSIVE(A_22, B_22, C_22, n/2)

Runnig Time 에 대한 점화식은 다음과 같다.

$T(n) = 8T(n/2) + \theta(1)$

다음 lecture에서 이 점화식을 푸는 방법을 알아보겠지만, $T(n) = \theta(n^3)$ 이며, 따라서 Divide-and-Conquer 알고리즘을 쓰더라도 점근적인 수행시간에 차이가 없음을 보여준다.

4.2 Strassen’s algorithm for Matrix Multiplication

$x^2 - y^2$ 을 계산하기 위해서는 두 번의 곱셈과, 한 번의 덧셈(뺄셈) 이 필요하지만 공식을 $(x+y)(x-y)$ 로 변형시키면, 한 번의 곱셈과 두번의 덧셈이 필요한다. 지금은 x, y가 스칼라이므로 두 접근 방식 모두 3번의 스칼라 연산이 필요하므로 차이는 없다. 그러나 x, y가 행렬인 경우, 곱하기의 비용이 더하기의 비용보다 크며 따라서 두 번재 방법이 더 좋은 성능을 보인다.

Strassen’s algorithm 은 $\theta(n^{lg7}) = \theta(n^2.81)$ 의 성능을 보이는 행렬 곱셈 알고리즘이다.

1. $n=1$ 이면 base case. 그 외의 경우엔 A, B, C를 $n/2 \times n/2$ 사이즈로 분할한다. $\theta(n^2)$ 소요.
2. 10개의 $n/2 \times n/2$ 행렬 $S_1 … S_{10}$ 을 만든다. 이는 1단계에서 만든 A, B의 부분행렬 8개의 합 또는 차이다. 행렬의 덧셈이므로 $\theta(n^2)$ 소요.
3. 7개의 $n/2 \times n/2$ 행렬 $P_1 … P_7$ 을 만든다. 그리고, $A, B$ 의 부분 행렬과, $S_i$ 의 행렬곱을 이용해 $P$ 를 계산한다. 이 행렬곱 과정은 재귀적 과정이다.
4. $P_i$ 행렬들의 다양한 조합을 더하거나 빼서 $C_{11}, C_{12}, C_{21}, C_{22}$ 를 구한다. 행렬의 덧셈이므로 $\theta(n^2)$ 소요.

즉, 행렬곱셈을 8번 하는 4.1의 예시와 비교하면, 행렬 곱셈 한 번을 상수 번의 행렬 덧셈과 바꾼 것이라 할 수 있다.

$T(n) = 7T(n/2) + \theta(n^2) = \theta(n^{lg7})$ 이다.