《算法导论》学习总结 — 3.第四章 && 第五章
因为《算法导论》第一部分1~5章的理论性太强，研究过多容易纠结，所以索性合起来快点讲过去。
第四章：
这一章讲的是递归式(recurrence)，递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。
本章讲了三种方法来解递归式，分别是代换法，递归树方法，主方法。
1.代换法(Substitution method)(P38~P40)
定义：即在归纳假设时，用所猜测的值去代替函数的解。
用途：确定一个递归式的上界或下界。
缺点：只能用于解的形式很容易猜的情形。
总结：这种方法需要经验的积累，可以通过转换为先前见过的类似递归式来求解。
2.递归树方法(Recursion-tree method)
起因：代换法有时很难得到一个正确的好的猜测值。
用途：画出一个递归树是一种得到好猜测的直接方法。
分析(重点)：在递归树中，每一个结点都代表递归函数调用集合中一个子问题的代价。将递归树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。
总结：递归树最适合用来产生好的猜测，然后用代换法加以验证。
递归树扩展过程：①.第二章2.3.2节分析分治法时图2-5(P21~P22)的构造递归树过程；②.第四章P41图4-1的递归树构造过程；这两个图需要好好分析。
3.主方法(Master method)
优点：针对形如T(n) = aT(n/b) + f(n)的递归式
缺点：并不能解所有形如上式的递归式的解。
具体分析：
T(n) = aT(n/b) + f(n)描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题的规模为n/b。
在这里可以看到，分治法就相当于a=2, b=2, f(n) = O(n).
主方法依赖于主定理：(图片点击放大)
图片可以不清晰，可以看书。
主定理的三种情况，经过分析，可以发现都是把f(n)与
比较。
第一种情况是
更大，第二种情况是
与f(n)相等，第三种情况是f(n)更大。
但是，这三种情况并未完全覆盖所有可能的f(n)：
第一种情况是f(n)多项式的小于
，而第三种情况是f(n)多项式的大于
，即两者相差的是
。如果两者相差的不是
，则无法用主定理来确定界。
比如算法导论P44最下面的
就不能用主定理来判断。
至于主定理的证明，有兴趣的可以拿笔在纸上推算，反正我这里是没看的，毕竟时间有限，要选择性的学习。
第五章：
本章是围绕一个雇佣问题展开的。
问题：有一批参与面试的人，你要一个个面试(面试每个人都要花费c1)，如果当前面试者比自己的助理能力强，则辞掉当前助理的，并把当前面试者提拔为助理(雇佣一个人要花费c2)，一直面试完所有人。
这里考虑的是面试所花的money，假设总共有N人参加面试，有M人被雇佣过，则花费O(N*c1 + M*c2)，因为参与面试的人员顺序是不确定的，所以要花费的money也是不确定的(N*c1是确定的，而M是不确定的，所以M*c2也是不确定的）。
首先介绍两个概念：
1.概率分析：指在问题的分析中应用概率的技术。
2.随机算法：如果一个算法的行为不只是由输入决定，同时也由随机数生成器所产生的数值决定，则成这个算法是随机的。
书上讲的理论性有点强，我这里用自己的话来说下：
首先说下概率分析，因为前面讲到过：雇佣所需的花费与输入序列有关，有N个面试人员(考虑每个人的能力不一样)，则一共有N!中排列情况(即每种排列出现的概率是1/(N!))，于是假设每种排列花费Ti元，则所有供花费：
T1/(N!) + T2/(N!) + … + TN/(N!)。
其实这里可以结合高中学的正态分布来理解，都是讲的每种情况出现的概率，思想差不多，所以这里也不需要什么概率论的知识，都是一些常识。
顺便补充一下：5.2节的指示器随机变量就是用的高中学的期望，用期望来表示概率。
再说下随机算法，对于上面概率分析时的方法，虽然面试人员的排列是不确定的。但是如果当排易做图定后，则所需花费也就确定了。而对于随机算法，就算排易做图定，其花费也是不确定的。即随机发生在算法上，而不是发生在输入分布上。这就是概率分析与随机算法之间的区别。
比如按书上的，可以给每个人员随机生成一个优先级，或者把每一个面试人员与其后的面试人员中随机一员交换，来产生一个随机的序列。
我以前总结过一些随机算法，有兴趣的朋友可以去看看：
html" target=_blank>1.《随机化算法(1) — 随机数》
2.《随机化算法(2) — 数值概率算法》
3.《随机化算法(3) — 舍伍德(Sherwood)算法》
补充：综合编程 , 其他综合 ,
