왜 갑자기 재귀?

• Divide and Conquer 알고리즘의 수행 시간을 분석하는 데 가장 자연스러운 접근법.

Methods for solving Recurrences

1. Brute-force method
2. Substitution method
3. Recursion tree method
4. Master method

Inequality Recurrences

만약 T(n) = 2 * T(n/2) + Theta(n) 이런 식으로 주어졌다면 Theta notation 사용이 가능하지만, 부등식일 경우 불가능하다.

• T(n) <= 2 * T(n/2) + Theta(n)
  -> 상한이 주어졌으므로 Big-O notation 사용.
• T(n) >= 2 * T(n/2) + theta(n)
  -> 하한이 주어졌으므로 Big-Omega notation 사용.

Brute-force Method

[ex 1]
T(n) = 2 * T(n/2) + n
	 = 2 * (2 * T(n/4) + n/2) + n = 2^2 * T(n/2^2) + 2n
     = 2 * (2 * (2 * T(n/8) + n/4) + n/2) + n = 2^3 * T(n/2^3) + 3n
     ...
     = 2^k * T(n/2^k) + kn = n*T(1) + log(n) * n
     = O(nlogn)
     
[ex 2]
T(n) = 2 * T(n/2) + n
T(n)/n = T(n/2)/(n/2) + 1
T(n/2)/(n/2) = T(n/4)/(n/4) + 1
...
T(2)/2 = T(1)/1 + 1

T(n)/n = T(1)/1 + 1 + 1 + 1 + ... + 1 + 1 = n + logn
T(n) = nlogn

Substitution Method

1. Guess the form of the solution.
2. Use mathematical induction to find the costants and show that the solution works.

• 만약 어떤 상수나 낮은 차수에 의해 기존의 증명하려던 식이 성립하지 않을 경우, 해당 차수를 관리할 수 있는 임의의 조작을 해주어야 한다.

Avoiding Pitfalls

귀납 증명은 "정확히 같은 형태"로 돌아와야 한다.

Changing Variables

점화식이 이상하면 변수 치환으로 바꿔라.

---

Recursion-tree Method

재귀 호출 구조를 트리 형태로 표현한 뒤, 각 레벨에서 발생하는 총 비용을 계산하고 이를 모두 더하여 전체 수행 시간을 구하는 방법이다.

---

Master Method

T(n) = a*T(n/b) + f(n)에서 a >= 1, b > 1인 상수이며 f(n)이 점근적으로 양수 함수일 때 사용하는 방법.

a가 1보다 크거나 같아야 하고, b가 1보다 커야 하는 이유가 뭘까.
결국 b가 1보다 커야 문제가 기존보다 작은 부분문제로 감소하기 때문이며, a역시 1보다 크거나 같아야 하는 이유는 주어진 문제를 적어도 1회 이상은 온전히 푸는 구조여야 Divide and Conquer의 구조를 유지하기 때문인가?

b는 몇 개로 쪼개질 것인가, a는 하위 문제의 개수가 몇 개인가를 담당해야 하기에 저런 조건을 세운 듯 하다.

n^log_b(a) 이 식은 결국 Divide and Conquer를 하는 과정에서 생기는 총 작업량을 의미한다. 또한, f(n)은 각 레벨에서의 노드 처리 작업량을 의미한다.

따라서, 두 식을 비교하여 더 큰 값이 있다면 해당 값이 다른 값을 무시할 수 있기에 해당 값이 답인 것이고, 두 값이 같다면 곱해주어야 한다.

Master method를 보면 Divide and Conquer 알고리즘의 핵심 골격을 알 수 있는 것이다.