分治策略（求解递归式的方法）

一、主定理：

主定理是最好用的方法，书本上以”菜谱“来描述这种方法的好用之处，它可以瞬间估计一个递推式的算法复杂度。

优点：针对形如T(n) = af(n/b) + f(n)的递归式

缺点：并不能解所有上述形式的递归式，有一些特殊情况，见下文分析。

分析：三种情况，如下图，着重看圈线的部分:

主定理.png

注意：1.ε符号，是在log之外。比log差一个常数量级ε。
2.条件是f(n)，结果是T(n)。

例题：求解递推方程
T(n) = 9T(n/3) + n
T(1) = 1
解答：
由主定理T(n) = aT(n/b) + f(n)得：
a = 9
b = 3
f(n) = n
∵ 代入主定理 f(n) = n^㏒₃9 = n²
又∵ f(n) = n. 当 ε = 1 时，f(n) = Ο(n^(2 - ε )) = Ο(n¹) = Ο(n)
此时，T(n) = Θ (n^㏒₃9) = Θ(n²)

二、递归树

image.png

举个例子：

T(n) = T(n/3) + T(2n/3) + n

其递归树如下图所示：

image.png
image.png

例题：求解递推方程
T(n)=T(n/2)+T(n/4)+cn

参考：
https://www.cnblogs.com/aademeng/articles/7044312.html
https://www.cnblogs.com/dear_diary/p/6851936.html
《算法设计与分析》-屈婉玲