符号介绍
$\Theta$
\[\Theta(g(n))=\{f(n): \exists c1,c2,n_0\ge0,\forall n\ge n_0 \ \ c1g(n)\le f(n)\le c2g(n) \}\]$O$
\[O(g(n))=\{f(n): \exists c,n_0\ge0,\forall n\ge n_0 \ \ 0\le f(n)\le cg(n) \}\]$\Omega$
\[\Omega(g(n))=\{f(n): \exists c,n_0\ge0,\forall n\ge n_0 \ \ 0\le cg(n)\le f(n) \}\]求解递归式
例：$T(n)=2T(n/2)+n$
要证$T(n)=O(nlgn)$
即证 $\exists c>0,T(n)\le cnlgn$
假设 $T(n/2)=O((n/2)lg(n/2))$
$T(n)=2O((n/2)lg(n/2))+n$
$\ \ \ \ \ \ \ \ \le cnlgn-cnlg2+n$
即可取合适的c使$T(n)\le cnlgn$
证毕
主方法求解
$T(n)=aT(n/b)+f(n)$
比较$f(n)\ n^{log_ba}$
若对某个常数 $\epsilon >0$ 有
$f(n)=O(n^{log_ba-\epsilon})$
则 $T(n) = \Theta(n^{log_ba})$
若 $f(n) = \Theta(n^{log_ba})$
则 $T(n) = \Theta(n^{log_ba} lgn)$
若对某个常数 $\epsilon>0$ 有$f(n) = \Omega(n^{log_ba+\epsilon})$，且对某个常数 c<1 和所有足够大的 n 有 $af(n/b) \le cf(n)$
则$T(n) = \Theta(f(n))$
本文共773字符