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

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

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

2-1. Asymtotic Notation

Asymptotic efficiency는, input size가 한계없이 커질 때 running time이 어떻게 늘어나는가를 말한다.

이 Asymptotic notation을 쓸 때는 어느 running time인지를 명확히 해야한다. (Worst case, best case, ...)

Θ-notation의 정의는 아래와 같다.

어떤 f(n)에 대해, 0 <= c1g(n) <= f(n) <= c2g(n) for all n >= n0로 표현될 수 있는 양의 상수 c1, c2, n₀가 존재하면,

f(n)은 Θ(g(n))이라고 한다. 즉 n₀ 이전값들이 그렇지 않더라도, 어떤 n0값 이후부터 f(n)이 g(n)의 상수변환으로 샌드위치 가능하면 Θ(g(n))이다.

이 때 g(n)은 f(n)의 asymptotically tight bound라고 한다. 이 Θ정의는 f(n)의 모든 멤버가 asymptotically nonnegative일 것을 요구한다.

O-notation의 경우 upper bound를 주고, Ω-notation의 경우 lower bound를 준다. 

즉, 어떤 양의 상수 n₀와 c에 대해 n₀의 우측 모든 f(n)값이 cg(n) 이하에 있으면 f(n) = O(g(n))이라고 한다.

어떤 책에서는 O-notation과 Θ-notation을 혼용하기도 한다.

1) Θ(g(n)) ⊆ O(g(n)) 이고, Θ(g(n)) ⊆ Ω(g(n))이다.

2) f(n) = Θ(g(n))이면 f(n) = O(g(n))이고 f(n) = Ω(g(n))이다. (필요충분조건)

소문자 o-notation의 경우 O-notation과 비슷하지만 모든 c에 대해 0 <= f(n) < cg(n)을 만족할 때를 말한다.

(대문자 O-notation의 경우 어떠한 c에 대해 0 <= f(n) <= cg(n)을 만족할 때를 말한다)

즉, 2n = o(n^2) 이지만 2n^2 != o(n^2) 이다. 

다시 말해 limn->∞ f(n)/g(n) = 0 이다. 

소문자 ω-notation의 경우, o-notation과 마찬가지다. 

o와 ω의 경우, 각각 asymptotically smaller 혹은 larger라는 표현을 사용할 수 있다.

이 notation들은 아래를 만족한다. N을 어떠한 notation이라고 표기하면,

1) Transitivitiy: f(n) = N(g(n))이고 g(n) = N(h(n))이면, f(n) = N(h(n))이다.

2) Symmetry: f(n) = Θ(g(n))이면 g(n) = Θ(f(n))이다. (필요충분)

3) Transpose symmetry: f(n) = O(g(n))이면 g(n) = Ω(f(n))이고, f(n) = o(g(n))이면 g(n) = ω(f(n))이다. (필요충분)

2-2. 알고리즘 디자인

다양한 알고리즘 디자인 방법들이 있다. Insertion sort에는 'incremental approach'를 사용했다.

이 섹션에서는 'divide-and-conquer'라는 방법을 알아본다. 이 방법의 장점은 worst case running time이 쉽게 계산된다는 것이다.

많은 유용한 알고리즘들은 구조상 recursive한 경우가 있는데, 일반적으로 divide-and-conquer 방식을 따른다.

Divide: 한 문제를 다수의 subproblem들로 나눈다.

Conquer: subproblem들을 recursive하게 푼다. 

Combine: 그 solution들을 합쳐 원래 문제의 solution으로 만든다.

이 방식을 통해 정렬 문제를 풀려면, merge sort 알고리즘을 사용한다.

Divide: n개의 시퀀스를 각각 n/2의 시퀀스 두개로 나눈다.

Conquer: 두개의 subsequence를 merge sort를 이용하여 recursive하게 푼다.

Combine: 두개의 subsequence를 합쳐 sorted 해를 얻는다.

Mergesort의 코드는 다음과 같다.

Mergesort (A, left, right)

if right == left then return

end if

middle = left + [(right - left)/2]

Mergesort (A, left, mid)

Mergesort (A, mid + 1, right)

Merge (A, left, mid, right)

처음 자료를 받아 반으로 나누고, 각 절반에 대해 recursion을 실행하고, 마지막으로 merge를 한다.

아래는 merge 함수의 pseudocode이다.

Merge (A, left, right, mid)

L = A[left, mid]

R = A[mid + 1, right]

Maintain two pointers pL, pR initialized to point to the first elements of L, R, respectively

while both lists are nonempty do

Let x, y be the elements pointed to by pL, pR

Compare x, y and append the smaller to the output

Advance the pointer in the list with the smaller of x, y

end while

Append the remainder of the non-empty list to the output.

L과 R이 sorted라고 가정하고, 각각의 첫번째 수를 비교해서 작은 것부터 차례로 A array에 넣는 함수이다.

2-3. Recurrence의 해

Recurrence의 Θ 혹은 O를 구하는 방법에는 세 가지가 있다.

Substitution method는 bound를 추정 후 수학적 귀납법을 사용해 그 추정이 옳음을 증명한다.

Recursion-tree method는 recurrence를 tree로 바꾼 후 푼다.

Master method는 T(n) = aT(n/b) + f(n) 형식의 recurrences에 bound를 부여한다. (a >= 1, b > 1)

위 형식은 자주 나오는데, 각 1/b 사이즈인 a개의 subproblem을 만들고, divide and combine step이 f(n)시간 걸리는 divide-and-conquer 알고리즘을 표현한다.

가끔 T(n) <= 2T(n/2) + Θ(n)과 같은 부등식이 나오면, 이는 T(n)의 upper bound만 지정해주므로 O-notation로 해를 표현한다.

>= 일 경우에는 그 반대로 Ω로 해를 표현한다.

실제로 recurrences를 풀 때, 작은 n에 대한 컨디션은 생략한다.

즉, n = 1일 경우 T(n) = Θ(1)이고, n > 1 의 경우 T(n) = 2T(n/2) + Θ(n)일 때, 전자는 생략한다.

이는 작은 n에 대해 T(n)은 상수라고 생각하기 때문이다. 

우리가 recurrences를 풀 때 floors, ceilings, 그리고 boundary condition들은 대체로 무시한다.

이들을 무시하고 해를 푼 후 그들이 영향이 있는지를 판단한다. 

그러나 그들이 영향을 준다면 그것을 반드시 알아야 한다.

2-4. Recursion-tree Method

Recursion tree에서, 각 교점(node)는 single subproblem의 cost를 표현한다.

그리고 각 층의 cost를 모두 더해 per-level costs를 구한 후, 모든 per-level costs를 더해 total cost를 구한다.

Recursion tree는 좋은 추정을 얻기 위해 사용하고, 이 추정을 substitution method로 검증해볼 수 있다.

아래는 T(n) = 3T(n/4) + Θ(n²⁾를 푸는 방식이다.

먼저, floor나 ceiling이 상관없다는 것을 가정하므로 Θ(n²)는 cn²로 대체한다.

그리고 편의를 위해, n이 4의 승수라서 모든 subproblem 사이즈가 정수라고 가정한다.

(a)에서 확장하여 (b)가 되고, T(1)에 도달할 때까지 이를 반복한다.

Depth를 0, 1, 2 순으로 매기면, depth i의 node에서 subproblem의 size는 n/4ⁱ 이다.

따라서 subproblem size는 n/4ⁱ = 1일 때 마지막에 도달하고, 따라서 i = log₄n 이다.

그러므로 level 0을 포함하여 이 tree는 log₄n + 1 레벨이 있다.

그 다음, 각 레벨의 cost를 보면 이전 레벨보다 3배로 node가 많으므로 depth i에서 3ⁱ개의 node를 가진다.

그리고 subproblem size는 1/4씩 감소하므로, depth i의 개별 node는 c(n/4ⁱ)² 이다.

이 둘을 곱하면, 각 층의 cost는 3ⁱc(n/4ⁱ)² = (3/16)ⁱn²c 가 된다.

마지막 층은 depth log₄n이므로 3^(log₄n) = n^(log₄3)개의 node를 가지며, 각 T(1)의 cost를 가진다.

T(1)는 상수로 가정하므로, 이는 곧 Θ(n^(log₄3)) 이다.

이제 전체 tree의 cost를 다 더하면, 

위와 같이 정리된다. 마지막 식은 조금 난잡한데, n이 무한히 증가한다고 가정하면 간단히 정리된다.

이제 우리는 T(n)이 O(n²)이라는 결론에 도달했다.

이 결론을 살펴보면, cn²의 coefficient는 decreasing geometric series를 형성하고, 그 합은 상수 16/13이 upper bound임을 알 수 있다.

그리고 root의 total cost에 대한 contribution이 cn²이고, 이는 constant fraction임을 알 수 있다. 즉, cost of root이 tree의 total cost를 dominate 한다.

따라서 Ω(n²)가 lower bound임을 알 수 있고, O(n²)가 upper bound임을 확인하면 Θ(n²)임을 증명할 수 있다.

이제 substitution method를 사용해서 O(n2)가 upper bound임을 확인하려면, 어떤 상수 d에 대해 T(n) <= dn² 임을 증명하면 된다.

그리고 마지막 부분은 d >= (16/13)c 인 한 성립된다.

또 하나의 예로, T(n) = T(n/3) + T(2n/3) + cn 처럼 T가 두 갈래로 나눠지는 예를 보자.

그림에서 보다시피 각 층마다 값을 더하면 cn임을 알 수 있다.

Root에서 leaf으로의 가장 긴 simple path는 n > (2/3)n > (2/3)²n > ... 이고, 

(2/3)ⁱn = 1 이려면 k = log_3/2n 이므로 tree의 높이는 log_3/2n 임을 알 수 있다.

직관적으로, 우리는 이 recurrence의 해의 최대치가 이 높이와 층합을 곱한 cnlog_3/2n = O(nlgn)임을 예상할 수 있다.

만일 이 tree가 완벽한 binary tree였다면, leaves의 개수는 2^층수, 즉 2^(log_3/2n) = n^(log_3/22) leaves를 가진다.

그러므로 모든 leaves의 total cost는 Θ(n^(log_3/22))이고, log_3/22는 1보다 크므로 Ω(nlgn)임을 알 수 있다.

그러나 이 tree는 완벽한 binary tree가 아니고, T(n/3)이 훨씬 빨리 감소하므로 tree의 아래층에는 많은 node가 빈다.

따라서 O(nlgn)이 성립한다고 추정할 수 있다. (더 엄밀하게 증명가능하지만 스킵하자)

Substitution method를 사용해 O(nlgn)이 upper bound임을 증명하면,

d >= c/(lg3 - 2/3)인 한 위는 성립한다.

2-5. Master Method

Master method는 T(n) = aT(n/b) + f(n) 형식의 recurrence를 푸는데 적합하다.

여기서 a >= 1, b > 1 인 상수들이고 f(n)는 asymptotically positive function이다.

Master method을 사용하기 위해서는 세 가지 케이스를 외워야 한다.

위의 형식은 n size 문제를 각각 n/b size인 subproblem a개로 나누는 걸 표현한다.

아래는 Master theorem의 정의이다. (Source: Introduction to Algorithms 3rd Ed., by Cormen, Leiserson, Rivest, Stein, p.94)

위를 간단하게 풀어쓰자면, T(n) = aT(n/b) + O(n^k)일 때 (a, b > 1이고 k >= 0) a와 b^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)

주의할 점은, Case 1에서 f(n)이 단순히 n^(log_ba) 보다 작아야하는 것이 아니라, polynomially smaller여야 한다.

즉, theorem 정의에서 보듯이 f(n)은 factor of n^ε로 n^(log_ba) 보다 asymptotically smaller여야 한다.

그리고 Case 3에서는 반대로 polynomially larger여야할 뿐만 아니라, regularity condition인 af(n/b) <= cf(n)을 만족해야 한다.

이 regularity condition은 우리가 마주하는 대부분의 polynomially bounded function들에 의해 만족된다.

이 Case들은 f(n)에 대한 모든 가능성을 커버하지 않는다. f(n)이 더 작지만 polynomially 작지는 않거나, 그 반대의 경우가 있다.

이런 경우라던지, Case 3의 regularity condition이 만족되지 않는다면 recurrence를 풀기 위해 master method를 사용할 수 없다.

이제 master method의 사용 예를 보자.

1) T(n) = 9T(n/3) + n

a = 9, b = 3, f(n) = n이므로 n^(log_ba) = n^(log₃9) = Θ(n²) 이다. 

ε = 1일 때 f(n) = n^(log_ba - ε)를 성립하므로, 이것은 Case 1에 해당하며, T(n) = Θ(n²)라고 결론 내릴 수 있다.

2) T(n) = T(2n/3) + 1

a = 1, b = 3/2, f(n) = 1 이고, n^(log_ba) = 1 이므로 f(n)과 같으며 Case 2다.

따라서 T(n) = Θ(f(n)lgn) = Θ(lgn) 이다.

3) T(n) = 3T(n/4) + nlgn

a = 3, b = 4, f(n) = nlgn 이고, n^(log_ba) = O(n^0.793) 이다.

ε ≒ 0.2일 때 f(n) = Ω(n^log₄3 + ε)을 만족하므로, Case 3에 해당한다.

충분히 큰 n에 대해 af(n/b) = 3(n/4)lg(n/4)이고, cf(n) = 3/4nlgn 로 두면, lg(n/4) < lgn 이 성립된다.

따라서 regularity condition이 만족되고, 해는 T(n) = Θ(nlgn) 이다.

4) T(n) = 2T(n/2) + nlgn

a = 2, b = 2, f(n) = nlgn이고, n^(log_ba) = n 이므로 f(n)이 더 크고, Case 3가 해당한다고 착각할 수 있다.

그러나 문제는 polynomially larger하지 않다는 것이다. f(n)/n^(log_ba) 의 ratio는 nlgn/n = lgn이고, 

이 lgn은 그 어떤 양의 상수 ε에 대해서도 n^ε보다 asymptotically 작다.