算法导论基础-几种递归式解法总结

---

# 1 代换法

求解步骤：
1. 猜测解的形式
2. 用数学归纳法求出解中的常数，并证明解是正确的。

---

# 2 递归树法

---

# 3 主方法 (常用)

递归通式：T (n)=aT (n/b)+f (n)

其中 f (n) 是非递归的，$a\ge1$,$b>1$
f (n) 渐进趋正（对于足够大的 n，$f(n)\ge0$)

考虑 f(n) 与 $n^{\log_{b}{a}}$,

情况一：f (n)<$n^{\log_{b}{a}}$-->O($n^{\log_{b}{a}-\xi}$)($\xi>0$)
$\therefore$ T(n)=$\theta$($n^{\log_{b}{a}}$)。

情况二：f (n)=$n^{\log_{b}{a}}$-->$\theta$($n^{\log_{b}{a}}\cdot (\lg_{}{n})^{k}$),$k\ge0$
$\therefore$ T(n)=$\theta$($n^{\log_{b}{a}}\cdot (\lg_{}{n})^{k}$)

情况三：f (n)>$n^{\log_{b}{a}}$-->O($n^{\log_{b}{a}-\xi}$)($\xi>0$),
$\because af(n/b)\le (1-\xi ^{'} )f(n)$
$\therefore T(n)=\theta (f(n))$

---