[Algorithm] Master Theorem - Recurrence relation(순환관계)

📎Time Complexity of Divide & Conquer algorithm

: 분할정복 알고리즘의 시간복잡도는 순환관계(recurrence relation)를 이용해서 계산할 수 있다.
일반적인 분할정복 알고리즘의 수행 시간 T(n)은 다음과 같은 식의 형태로 표현할 수 있다.

• T(1) = c, c는 양의 정수
• T(n) = aT(n/b)+O(n^d)

🔼 size가 n/b인 a개의 subproblem으로 나뉘며 subproblem '하나' 정복 시 O(n^d)시간이 소요되는 경우.

cf) d는 '상수'이다. d에는 어떤 값이 올지 모르지만 어떤 값이 와도 부등식으로 표현되기에 상관이 없다.

이 식을 정리하면 3가지 경우로 나누어 점근적 표기로 나타낼 수 있다.

• O(n^d), d>log b a (밑이 b)
• O(n^d*log b n), d = log b a
• O(n^log b a), d< log b a

cf) 식의 정리 과정에서 O(n^d)을 n^d로 표현 가능한데 이것은 "어차피 O-표기"할 거라서 가능한 것이다. 이미 O(n^d)도 점근적 표기라 정확한 값이 아니다.