复杂度计算

复杂度

$\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})$

排序