目次
計算量の一般化
$T(n) = \left\{ \begin{align} T(1) \to \Theta (1) \qquad if\quad n=1 \\aT(\frac{n}{b})+f(n)\qquad if\quad n>1 \end{align} \right.$
ケース1：$f(n)=O (n^{\log_b a – \epsilon })$の時
$T(n)\Theta (n^{\log_b a})$
ただし、$b > 1, a\geq 1$
ケース2：$f(n)=\Theta (n^{\log_b a })$の時
$T(n)=\Theta (n^{\log_b a \lg n }$
ただし、$b > 1, a\geq 1$
ケース3：$f(n)=\Omega (n^{\log_b a +\epsilon})$の時
この場合は、同時に$af(\frac{n}{b})\leq cf(n), c<1$を満たす必要がある。
この時、
$T(n)=\Theta (f(n))$
二分探索の計算量
$T(n) =T(\frac{n}{2}) +\Theta (1)$
$n^{\log_b a} = n^{\log_2 1}=1$
$f(n)=\Theta (n^{\log_b a}) = \Theta (1)$
ケース２より、
$T(n) =\Theta (\Theta (1) \lg n)=\Theta(\lg n)$
行列の積演算
$T(n) = 7(T(\frac{n}{2})) + \Theta (n^2)$
$2 <\log_2 7 <3$より、
$f(n) =O(n^{\log_2 7 -\epsilon})$
ケース１より、
$T(n) = \Theta (n^{\log_2 7})$
