替换函数（SubstitutionFunction）

在对算法进⾏分析的时候，常常要计算该算法时间复杂度的近似表⽰(Asymptotic Notation)。然⽽在求取的过程中，常常遇到递归函数，使求解陷⼊困境。

⼀般的，解决上述递归的⽅法有三种：替换函数(Substitution Function)，迭代(Iteration)和主定理(Master Thorem)。这⾥介绍替换函数(Substitution Function)。替换函数(Substitution Function)

替换函数(Substitution Function)的步骤⼀般有三：1. 猜测(Guess)解的形式2. ⽤数学归纳法验证(Verify)3. ⽤满意的常量来解答(Solve)

⾸先猜测(Guess)⼀般我们基于下表这些常⽤的Efficiency Class

类1log nnn22n

名称常数对数线性

注释

很少使⽤，可以忽略输⼊查找整个输⼊列表

n log nn-log-n很多分治法算法

⼆次指数

内嵌两个循环的算法⽣成某⼀个集合的所有⼦集

对于后两步的说明可以⽤⼀个例⼦来表现：T(n) = 4T(n/2) + n- 猜测T(n)＝O(n3)

- 假设对于任何kT(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)。注意使⽤减去⼩的项来加强数学归纳法的假设- 假设对于任何kT(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)