『Disclaimer: 본 글은 대학원의 데이터과학 알고리즘 수업 및 데이터과학 입문서적에 관한 공부 내용을 정리하는 시리즈입니다. 

본 내용은 필자가 전부 직접 요약하여 적은 개인 노트이며, 개인 공부 및 복습이 주목적일 뿐, 상업적 의도는 없습니다. 

Source: Introduction to Algorithms 3rd Ed., by Cormen, Leiserson, Rivest, Stein』

3-1. Strassen's Algorithm for Matrix Multiplication

3-1-1. 일반적인 행렬곱

A와 B가 n x n 행렬이라고 하면, 그 product C을 구하기 위해서는 최소한 n²의 계산을 해야한다.

일반적인 정사각 행렬의 곱셈은 다음과 같이 진행된다.

1 n = A.rows

2 let C be a new n x n matrix

3 for i = 1 to n

4  for j = 1 to n

5 c_ij = 0

6 for k = 1 to n

7  c_ij = c_ij + a_ik · b_kj

8 return C

Line 7의 계산은 constant time이 걸리기 때문에 이 precedure는 θ(n³) 이 걸린다. 

그리고 이를 이길 수 있는 알고리즘이 있는데 바로 Strassen이 고안한 알고리즘으로, θ(n^lg7)이 걸린다.

3-1-2. 간단한 divide-and-conquer 행렬곱

먼저, 간단한 divide-and-conquer 알고리즘을 생각해 보자.

각 A, B, C를 n/2 x n/2의 크기를 가진 작은 매트릭스로 4등분한다.

그러면 알고리즘은 아래와 같다.

Matrix-Multiply-Recursive(A, B)

1 n = A.rows

2 let C be a new n x n matrix

3 if n == 1

4 c11 = a11 · b11

5 else partition A, B, and C

6 C11 = MMR(A11, B11) + MMR(A12, B21)

7 C12 = MMR(A11, B12) + MMR(A12, B22)

8 C21 = MMR(A21, B11) + MMR(A22, B21)

9 C22 = MMR(A21, B12) + MMR(A22, B22)

10 return C

Line 5에서 partition은 새로운 12개의 n/2 x n/2 행렬을 copy하면 θ(n²) 이 걸리지만, index calculation을 사용하면 θ(1)이 걸린다.

Line 6-9에서 MMR은 8번 부르므로 8T(n/2)가 걸린다. 

또한 Line 6-9에서 총 4번의 덧셈이 행해지는데, 각 n²/4 씩 걸리므로 총 θ(n²) 이다. 그러면,

T(n) = θ(1) + 8T(n/2) + θ(n²) = 8T(n/2) + θ(n²) 이다. 그리고 Base case T(1) = θ(1) 이다.

이를 master theorem을 적용해 보자. 다시 한번 master theorem을 적어보면,

T(n) = aT(n/b) + O(n^k)일 때,

Case 1. a > b^k면 T(n) = O(n^(log_ba))

Case 2. a = b^k면 T(n) = O(n^klogn)

Case 3. a < b^k면 T(n) = O(n^k)

여기서 a = 8, b = 2, k = 2이므로, Case 1에 해당하고, 따라서 O(n³)이다. 더 엄밀히 적용하면 θ(n³)이다.

즉, 이 divide-and-conquer 방식은 일반적인 matrix 곱 방식보다 더 빠르지 않다.

여기서 잠시 짚고 넘어가야할 것은, asymptotic notation은 O(4n²)를 O(n²)료 표기하지만, T(n)은 그래선 안된다는 것이다.

3-1-3. Strassen's Method

Strassen의 방식은 아래의 단계를 거친다.

1. A, B, C를 n/2 x n/2 행렬로 나눈다. Index calculation으로 θ(1)이 걸린다.

2. S₁에서 S₁₀까지의 10개의 행렬을 만든다. 1번 단계에서 만든 매트릭스의 합이거나 차인 n/2 x n/2 매트릭스 들이다. 이 모든 것은 θ(n²)이 걸린다.

3. 1, 2번 단계에서 만든 행렬들을 recursively 곱해 P₁, ... , P₇의 7개 행렬을 만든다. 

여기서 중간식을 계산하면 되고, 가장 우측식은 그냥 중간식이 무엇인지 풀어서 표기한 것이다.

4. P_i 행렬들을 이용해 C를 구한다. 이에는 θ(n²)이 걸린다.

 

이 방식을 사용하면, T(1) = θ(1), T(n) = 7T(n/2) + θ(n²)이 되고, 최종적으로 T(n) = θ(n^lg7)이 걸린다.

3-2. Linked Lists

Linked list는 object들이 linear order로 정렬된 data structure다.

Array는 array indices로 linear order가 정해지는 반면, linked list는 각 object의 pointer로 정해진다.

Doubly linked list L의 각 element는 attribute key, next, prev를 가진다. next와 prev는 각각 다음, 이전 데이터를 가리킨다.

만약 x.prev = NIL 이면 첫번째 element, 즉 head고, x.next = NIL 이면 tail이다. 

L.head는 list의 head이며 L.head = NIL이면 그 리스트는 empty다.

리스트는 1) singly linked 혹은 doubly linked일 수 있고, 2) sorted or unsorted일 수 있으며, 3) circular or non-circular일 수 있다.

1) Singly linked일 경우, 각 element의 prev pointer를 생략한다. 

2) Sorted면 linear order of list가 각 element에 저장된 key들의 linear order와 동일하다. Minimum element가 head고 maximum element가 tail이다.

3) Circular list에서는 head.prev = tail.next다.

이 섹션의 나머지 부분에서 나오는 list는 unsorted고 doubly linked라고 가정한다.

List-Search(L, k)는 List L에서 key k를 가진 첫 element를 simple linear search를 통해 찾고, 해당 element로의 pointer를 리턴한다.

key k를 가진 오브젝트가 없으면 NIL을 리턴한다. 

List-Search(L, k)

1 x = L.head

2 while x != NIL and x.key != k

3 x = x.next

4 return x

n개의 오브젝트를 가진 리스트를 찾으려면 List-Search는 worst case θ(n)이 걸린다.

key attribute이 이미 세팅된 x가 주어지면, List-Insert는 x를 linked list 앞에 붙인다.

List-Insert(L, x)

1 x.next = L.head

2 if L.head != NIL

3 L.head.prev = x

4 L.head = x

5 x.prev = NIL

List-Delete 프로시져는 element x를 linked list L에서 제거한다. x에의 pointer가 주어지면, x를 splice해서 꺼낸다.

List-Delete(L, x)

1 if x.prev != NIL

2 x.prev.next = x.next

3 else L.head = x.next

4 if x.next != NIL

5 x.next.prev = x.prev

List-Delete는 θ(1)에 실행되지만, key가 주었을 때 최악의 경우 List-Search를 θ(n)을 사용해서 element를 찾아야 한다.

만약 list의 head와 tail의 boundary condition을 무시할 수 있다면, List-Delete는 매우 간단해질 것이다.

List-Delete* (L, x)

1 x.prev.next = x.next

2 x.next.prev = x.prev

Sentinel은 boundary condition을 간단하게 만드는 dummy object이다. 

예를 들어 어떤 리스트 L에, NIL을 표현하지만 다른 모든 object와 같은 attribute들을 가지는 object L.nil을 준다고 하자.

그러면 regular doubly linked list를 circular doubly linked list with sentinel로 변환한다. 

여기서 sentinel L.nil은 head와 tail에 사이에 있으며, L.nil.next는 head를 point하고 L.nil.prev는 tail을 point한다.

따라서 L.head나 L.tail이라는 attribute 자체를 제거하고 L.nil.next 혹은 L.nil.prev로 대체할 수 있다.

이를 사용할 경우, List-Search는 그대로지만, NIL과 L.head에 대한 참조만 변한다.

List-Search* (L, k)

1 x = L.nil.next

2 while x != L.nil and x.key != k

3 x = x.next

4 return x

List-Insert는 조금 더 간단해진다.

List-Insert* (L, k)

1 x.next = L.nil.next

2 L.nil.next.prev = x

3 L.nil.next = x

4 x.prev = L.nil

Sentinel이 data structure operation의 asymptotic bounds를 변화시키는 것은 드물다.

그러나 constant factor는 감소시킨다. 여기서는 O(1) 시간만 줄이지만, 다른 상황에서 n과 n²의 coefficient를 감소시킬 수 있다.

또한 code가 더 명료해진다.

하지만 반면 수많은 작은 리스트가 있을 경우, sentinel들에게 주어지는 extra storage가 많은 메모리를 소모할 수 있다.