시간 복잡도 분석 연습

Master Theorem

점화식이 T(n) = rT(n/c) + O(f(n))의 형태일 때

case1. f(n) = Ω($𝑛^{log_c r}$) 이면 T(n) = O(f(n))

case2. f(n) = Θ ($𝑛^{log_c r}log^k n$) 이면 T(n) = O(f(n)logn)

case3. f(n) = O($𝑛^{log_c r}$) 이면 T(n) = O( $𝑛^{log_c r}$ )

 

T(n) = 2T(n/2) + O(n) => $n^{log_2 2} = n^1$, f(n) = n => case2 => O(nlogn)
T(n) = T(n/2) + O(n) => $n^{log_2 1} = n^0$, f(n) = n => case1 => O(n)
T(n) = T(n/2) + O(1) => $n^{log_2 1} = n^0$, f(n) = 1 => case2 => O(1logn)
T(n) = 4T(n/2) + O(n) =>  $n^{log_2 4} = n^2$, f(n) = n => case3 =>O($n^2$)
T(n) = 3T(n/2) + O(n) => $n^{log_2 3} = n^{1.x}$, f(n) = n => case3 => O($n^{log_2 3}$)
T(n) = T(n/3) + O($n^2$) => $n^{log_3 1} = n^0$, f(n) = $n^2$ => case1 => O($n^2$) 
T(n) = 2T(n/2) + O(nlogn) => $n^{log_2 2} = n^1$, f(n) = nlogn => case2(k=1) => O($nlog^2 n$)
T(n) = T(n/3) + T(2n/3) + O(n)

Master Theorem  사용 못 함=> recursion tree 사용 => 두 개의 분기로 나뉨 (n/3, 2n/3) => 계속해서 각각 똑같은 비율로 나뉨 => 따라서 각 층 마다 합을 구하면 = n => 최종적으로 O(nlogn)

(2/3)^n = 1 -> 깊이 log_3/2 n

 

T(n) = T(n - 2) + T(2) + O(n)
= T(n-2) + O(n) = T(n-2) + cn = T(n-4) + c(n-2) + cn = ... => T(n) = O($n^2$)

A(n) = 2A(n/4) + $\sqrt{n}$ -> case2 -> O($\sqrt{n}logn$)
B(n) = 2B(n/4) +n -> case1 -> O(n)
C(n) = 2C(n/4) + $n^2$ -> case1 -> O($n^2$)
D(n) = 3D(n/3) + $\sqrt{n}$ -> case3 -> O(n)
E(n) = 3E(n/3) +n -> case2 -> O(nlogn)
F(n) =3F(n/3) + $n^2$ -> case1 -> O($n^2$)
G(n) =4G(n/2) + $\sqrt{n}$ -> case3 -> O($n^2$)
H(n) =4H(n/2) +n -> case3 -> O($n^2$)
I(n) =4I(n/2) + $n^2$ -> case2 -> O($n^2logn$)
J(n) = J(n/2) + J(n/3) + J(n/6) + n

 

깊이:  log n, 문제 크기 n으로 일정 -> O(nlogn)

 

K(n) = K(n/2) + 2K(n/3) + 3K(n/4) + $n^2$
문제 크기 $n^2$ -> $95/148n^2$ -> ... -> $cn^2$ 비례 -> 공비가 1보다 작은 등비수열 -> $n^2(1 + 95/148 + ...)$ -> O($n^2$) 

L(n) = L(n/15) + L(n/10) + 2L(n/6) + $\sqrt{n}$
$\sqrt{n}$ -> $c\sqrt{n}$ -> ... -> $\sqrt{n}$에 비례 -> 공비가 1보다 큰 등비수열 -> 노드의 개수와 같음

=> tree 높이 = $log_6 n$ (n/6이 더 깊이 내려감. 나머지도 걍 있다고 치고 이걸 기준으로 계산)

=> leaf: 1, 4, 4^2,... $4^{log_6 n}$ -> $n^{log_6 4}$  -> O($n^{log_6 4}$)

트리가 내려갈 수록 노드합이 늘거나 줄거나 일정할 때 다름