在对算法进行分析的时候，常常要计算该算法时间复杂度的近似表示(Asymptotic Notation)。然而在求取的过程中，常常遇到递归函数，使求解陷入困境。
一般的，解决上述递归的方法有三种：替换函数(Substitution Function)，迭代(Iteration)和主定理(Master Thorem)。这里介绍替换函数(Substitution Function)。
替换函数(Substitution Function)替换函数(Substitution Function)的步骤一般有三：
1. 猜测(Guess)解的形式
2. 用数学归纳法验证(Verify)
3. 用满意的常量来解答(Solve)
首先猜测(Guess)一般我们基于下表这些常用的Efficiency Class
| 类 | 名称 | 注释 |
| 1 | 常数 | 很少使用，可以忽略输入 |
| log n | 对数 | |
| n | 线性 | 查找整个输入列表 |
| n log n | n-log-n | 很多分治法算法 |
| n2 | 二次 | 内嵌两个循环的算法 |
| 2n | 指数 | 生成某一个集合的所有子集 |
对于后两步的说明可以用一个例子来表现：
T(n) = 4T(n/2) + n
- 猜测T(n)＝O(n3)
- 假设对于任何k<n有T(k) <= ck3用数学归纳法证明T(n) <= cn3
T(n) = 4T(n/2) + n <= 4c(n/2)3 + n = cn3/2 + n = cn3 - (cn3/2 - n) <= cn3 (如果c >= 2 且 n>=1)
那么T(n)＝O(n3)
注意：证明数学归纳法的步骤中，使用(你需要的结果) - (某个式子) > 0
求取比较紧的一个上界，试试T(n)=O(n2)。
注意使用减去小的项来加强数学归纳法的假设
- 假设对于任何k<n有T(k) <= c1k2 - c2k,
T(n) = 4T(n/2) + n <= 4(c1(n/2)2 - c2(n/2)) + n = c1n2 - 2c2n + n = c1n2 - c2n - (c2n - n) <= c1n2 - c2n
那么T(n) = O(n2)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。