Lesson7：分治法

想必之前其实就有思考过类似的问题，这节课是总结与提升。

T(N) = aT(N/b) + f(N) 是基本分治的公式，其中a、b分别为划分出的子问题数量与子问题的收缩，f(N)为merge合并子问题的复杂度。

代入法

意思就是根据经验来猜出时间复杂度，然后代入验证。

先猜测上界再用数学归纳法证明

T(N) = 2T(⌊N/2⌋)+N

猜测一：T(N)=O(NlogN)

猜测二：T(N)=O(N)

T(N)=2T(m)+N≤2c⌊N/2⌋+N≤cN+N=(c+1)N

可以发现T(N)对应的N常数并没有保持，所以猜测二不成立，但是可以利用之来猜正确的猜测一。

换元法：T(n)=2T(sqrt(n))+logn

那我们就令logn=m，因此T(2^m) = 2T(2^m/2) + m

S(m) = T()(2^m) = 2S(m/2) + m

因此S(m) = mlogm

代入就有T(n) = O(logn*loglogn)

递归树法

完全递归树

叶子节点总是有n^log_ba个，时间复杂度就是O(N^log_ba)，层数无其他限制就为log_bN-1层(去除叶子的那层)

不完全递归树

主定理法

其实关键都在于比较 n^log_ba 和 f(n) 之间的关联，如果前者大，则前者 “掌控了” 整个时间复杂度，所以时间复杂度就是 T(n) = aT(n/b) 对应的复杂度，这也很符合直观，因为此时 a 比较大，分叉比较多，树比较大（结合前面递归树的例子），所以更大的复杂度会落在叶子上；反之后者大则每一层的复杂度 “掌控了” 整个时间复杂度，故整体时间就是 f(n) 级别的。这就是主定理的含义，谁主持(master)了整个时间复杂度。

不能用主定理的原因是对于任意a>0，我们知道n^a > logn，因此我们找不到情况1中的a，此方法无效，这就是所谓的"间隙"。

这甚至还有更强的表达。