Preview
这里详细讲讲分治策略（虽然这个明显应该算后面的「分析技术」吧……）第五章概率分析就不讲了，基本都是离散的问题。
Keywords: 最大子数组问题 Strassen 递归式
先修知识：
假想你知道未来三十天的股票价格，你需要写一个算法来求出何时买何时卖来保证收益最大化——显然我们首先可以得到一个数组，每一个index代表天数，每一个value代表与这一天股票价格与前一天的价格差值(第0天是0)。那么我们的问题就可以转化为寻找这个数组的和最大的非空连续子数组。这样的连续子数组被叫做最大子数组。
最大子数组
//书上讲得很乱，理解了半天…… 最大子数组应该有以下值得注意的地方：
- 原数组必包含负数
- 一个原数组可能有多个最大子数组
- 我们可以利用之前计算出的子数组和来计算当前子数组的和，使得每次计算子数组和的时间为O(1)，因此暴力求解方法所耗费的时间为O(n^2)
现在回到我们的股票问题。为了更快地得到最大子数组，我们可以用分治法的思想来考虑这个求解问题。这并不完全像以前学的最大值最小值。
连续子数组存在下列三种情况：
- 完全在A[low, mid]中
- 完全在A[mid+1, high]中
- 跨越中点mid
对于第一二种情况是很简单的，你把目前求的最大子数组直接求和成一个数，其他的子数组也求和成一个个数，看成用分治求解一个数组的最大值就行了。比如，1，2，-3，-4，对于最大子数组中，数的个数为2的情况，就可以把它看成分治求解3，-7。数的个数>1时单情况复杂度肯定小于nlogn，再迭代考虑数的个数=数的个数+1的情况，求和的数据可以在O（1）时间内继承上个情况的数据，多个情况相加最后得到nlogn。
这种理解方式跟书上不太一样，但是我认为比书上会好理解得多，欢迎捉虫。
显然地，任何的第三种情况都可以分割为第一+第二种情况，只是要求边界必须包含mid和mid+1，然后合并。（伪代码略）这样这个问题就变成了在一定条件下寻找最大子数组。伪代码思路：
- 判断只有一个元素的base case
- 选定mid，左递归调用，右递归调用
- 对第三种情况的数组分割+分治考虑，直接return一个处理好的极大子数组
- 比较value
分治算法分析
承接股票问题。书上给的 T(n)= Θ(1) + 2T(n/2) + Θ(n) + Θ(1) = 2T(n/2) + Θ(n)
这就是T(n) 在n > 1 时的递归情况。然而我之前理解的方式和它不太一样，它原来的分治算法是真的很难理解……不过反正都是nlogn，就懒得管那么多了。这个T(n)递归式就后面拿来分析主方法求解好了。而且书上也说了，存在一个更好的非递归，线性时间的算法(习题4.1-5)
谈点别的。分治法不仅仅只用于一分为二。它的核心思想是分和治，至于怎么分怎么治都可以进一步优化。一分为多的通用递归式推导：
摘自《算法设计与分析基础(第三版)》的附录B, P376
Ps.似乎只有在一分为质数个子问题的情况才有讨论通用递归式的意义
Strassen算法
前排提示：这一个算法实战没卵用
Cij = (上面n)∑(下面k=1) Aik × Bkj
这是矩阵中乘积的公式。当然，我们知道在算法里面的实现无非是三个for循环，类似于求传递闭包的算法。直觉告诉我们矩阵的乘法算法就应该耗费n^3级别的时间，然而Strassen算法可以把运行时间缩到n^log7的级别，约为n^2.81。
先假设我们的矩阵A和B都是2^k 乘 2^k，显然矩阵C也是同等规模。因为2^k本身，那么所有的大矩阵都应该由四个子矩阵构成，每个子矩阵又由四个子矩阵构成，如下：
大矩阵 =
子矩阵 子矩阵
子矩阵 子矩阵
RECURSIVE(A,B)
C11 = RECURSIVE(A11, B11) + RECURSIVE(A12, B21)
C12 = RECURSIVE(A11, B12) + RECURSIVE(A12, B22)
C21 = RECURSIVE(A21, B11) + RECURSIVE(A22, B21)
C22 = RECURSIVE(A21, B12) + RECURSIVE(A22, B22)
return C
//其他部分省略
上面这个算法除初始化之外，每一次循环有八次递归调用，再又因为这四次矩阵加法中，每个矩阵包含(n/2)^2个元素（n指C的边的规模）因此 ` T(n) = Θ(1) + 8T(n/2) + Θ(n^2) = 8T(n/2) + Θ(n^2) `
这就是n > 1的时候的T(n)递归式啦。这个递归式的常数因子「8」还是挺烦的，而且其实算出来的用时还不如老老实实n^3（变相n^log8），所以Strassen方法才刚刚开始呢——
1.按矩阵分成子矩阵的公式将A，B和C分解为n/2 × n/2 的子矩阵，采用下标计算方法，耗时Θ(1)
2.创建10个n/2 × n/2的矩阵S1，… , S10，每个矩阵保存步骤1中创建的两个子矩阵的和或差，耗时Θ(n^2)（原因同上面那个算法里的n^2）
3.用步骤1中创建的子矩阵和步骤2中创建的10个矩阵，递归计算7个矩阵积P1，… , P7。每个矩阵积都是n/2 × n/2的。
4.通过P矩阵的不同组合进行加减运算，就能得出矩阵C的四个子矩阵，花费时间Θ(n^2)
别慌。其实我现在写的时候也看不太懂……（书上原话：这可能是本书陈述最不充分的地方了，虽然我觉得这本书那些充分的陈述我也看不懂）好了，接下来是本书最最最魔法的时刻了，做好心理准备：
S1=B12-B22 ; S2=A11-A12 ; S3=A21+A22 ; S4=B21-B11 ; S5=A11+A22 ; S6=B11+B22 ; S7=A12-A22 ; S8=B21+B22 ; S9=A11-A21 ; S10=B11+B12 ; P1=A11 x S1 ; P2=A11 x B22 ; P3=S3 x B11 ; P4=A22 x S4 ; P5=S5 x S6 ; P6=S7 x S8 ; P7=S9 x S10 ; C11=P5+P4-P2+P6 ; C12=P1+P2 ; C21=P3+P4 ; C22=P5+P1-P3-P7 ;
按上述步骤做，最后的C一定能求出来，实质在于乘法分配律ax(b+c)=axb+axc，前算式比后算式少一个运算符……在n > 1的时候递归式是T(n) = 7T(n/2)+ Θ(n^2)。
别的细节就不要再追究了，书上连证明都没有，这个算法已经浪费我一个晚上了……
另外渐进复杂性最优的矩阵乘法算法运行时间达到了O(n^2.376)，估计那个还要更变态。我一点也不喜欢这种缺乏艺术感的算法。
三种求解递归式的方法
递归式的本质是分段函数，不过会有一个调用自己的「段」来实现递归。无论「段」对自变量如何划分，实际上都很难处理奇偶数的问题。奇数状态下两个子问题的规模都不会是n/2。不过我们一般都忽略这种细节，哪个甲方和用户会在乎呢……
代入法
代入法本质是先猜测递归式的解的形式，然后再通过别的操作带入这个猜测解。下面做个示范：
假设有递归式 ` T(n) = 2T(n/2) + n ` 我们按照下列步骤操作：
- 猜测解的形式为T(n) = O(nlogn)
- 显然，对于常数c >=1，有T(n) <= c nlogn。证明这个不等式就可以证明猜测正确。
- 显然，对于n = n/2 的情况，有T(n/2) <= c(n/2)log(n/2)
- 将第三步中的式子代入递归式，得到T(n) <= 2c(n/2)log(n/2) + n
最后自己算吧，右式能够转化成c nlogn就可以证明猜测正确了。
一些细节：对于不好猜测的递归式可以先判断上界和下界，然后慢慢收敛到渐进紧确界。猜测的解只是用于迈出第一步，当发现证明过程困难的时候应该适当地修改猜测的解。
递归树法
参考上一篇文章里画的图的上半部分，如果对每一层每一位置所处的情形都用消耗的T来取代，再在该层右边写上这一层每一位置消耗的T的总和，那么这就是所谓的递归树。其实递归树无非是把前几次递归的情况分析清楚，以便于做出更好的猜测，于是代入法就可以继续验证啦。当然不用代入法继续做的话，那就可以类比直接解归并排序的递归式。但是一旦涉及到复杂得多的递归式解法，只用递归树法会要求很强的数学能力……
主方法
T(n) = aT(n/b) + f(n)
这是一种比较通用的递归式形式。举个例子，描述Strassen算法的递归式的时候，a = 7, b = 2, f(n) = Θ(n^2)。我们在用主方法解递归式的时候，首先要了解到主方法依赖于下面的定理：
令a>=1，b>1，f(n)是一个函数，有非负整数上的递归T(n) = aT(n/b) + f(n)，其中我们将n/b解释为向上或向下取整，那么T(n)有如下渐进界：
- 若对某个常数m>0有f(n) = O(n^(logb(a-m)))，则T(n) = Θ(n^(logb(a)))
- 若f(n) = Θ(n^(logb(a)))，则T(n) = Θ(log(n) x n^(logb(a)))
- 若对某个常数m>0有f(n) = Ω(n^(logb(a+m)))，且对某个常数c<1和所有足够大的n有af(n/b)<=cf(n),则T(n) = Θ(f(n))
代数证明就省了吧，不会有正常人感兴趣的。
上述三种对f(n)的判定实际上是拿f(n)跟n^(logb(a))进行比较。注意这个比较，一定要是多项式意义上的比较，也就是说在判断大于和小于的时候，不仅要求f(n)渐进n^(logb(a))，还要求要相差一个因子n^m。
T(n) = 2T(n/2) + nlogn 就是一个典型的不适用主方法的例子。我们看f(n) = nlogn确实渐进大于nlogb(a) = n，但这并不是多项式意义上的渐进，nlogn和n的比值，即logn，是要渐进小于n^m的，也就是说递归式落入了 渐进大于 和 等于 这两种情况之间的间隙。实际上上面主定理提到的三种情况之间都存在间隙，所以使用主方法固然方便快捷，也要小心弊端。
关于logn渐进小于n^m的证明
//主方法还是挺重要的，面试的时候解递归式很实用。
题目答案
先占着
最大子数组和Strassen算法要不要这么劝退啊……前面有的地方是真的是讲得莫名其妙。不过退一步讲，也许后面的红黑树最大流什么的更加劝退呢……