复杂度
$\Theta $: Theta, 渐进紧确界
$O$: Omicron, 渐进上界($\omicron$: 非渐进上界)
$\Omega$: Omega, 渐进下界($\omega$: 非渐进下界)
递归树法
代入法
$T(n) = 2T(n / 2)+n$
$猜测:n\lg{n}$
带入:
$T(n) \leq 2(n/2 \lg{(n/2)} )+n = n\lg{(n/2)}+n$
$= n\lg{n}-n\lg{2}+n \leq n\lg{n}$
主方法
$$ T(n) = aT(n/b) + O(n^d), for \ a \geq 1, b > 1, d \geq 0\\ T(n) = \theta(n^{log _b^a}), d < log _b^a \\ T(n) = \theta(n^dlg _n), d = long _b^a\\ T(n) = \theta(n^d), d > log_b^a $$
对于: $T(n) = aT(n/b) + f(n)$
-
若: $对于常数\epsilon > 0, f(n) = O (n^{\log_{b}^{a-\epsilon}})$, 则: $T(n) = \Theta(n^{\log_{b}^{a}})$ (理解为比$f(n)$大)
例如: $T(n) = 9T(n/3) + n$, 有$n^{\log_{b}^{a}} = n^2$, 则$T(n) = \Theta(n^2)$
-
若: $f(n) =\Theta(n^{\log_{b}^{a}})$, 则$T(n) = \Theta(n^{\log_{b}^{a}}\lg{n})$ (理解为等于$f(n)$)
例如: $T(n) = T(2n/3) + 1$, 有$n^{\log_{b}^{a}} = n^{\log_{3/2}^{1}} = n^0 = 1$, 则: $T(n) = \Theta (\lg{n})$
-
若: $对于常数\epsilon > 0, T(n) = \Omega(n^{\log_{b}^{a-\epsilon}}), 且对于某个常数c<1和所有足够大的n有af(n/b) \leq cf(n)$, 则: $T(n) = \Theta(f(n))$
例如: $T(n) = 3T(n/4)+n\lg{n}$, 有 $n^{\log_{b}^{a}} = n^{\log_{4}^{3}} = n^{0.739}$ , 所以$T(n) = \Theta (n\lg{n})$