算法基础笔记
要常去思考书中算法是怎么想出来的!
思想总结
1. 分治法(合理划分,merge时可节省时间时才可行):4.2
2. 循环不变式:5 | 9.3
初始化、保持、终止
3. 稳定排序算法的作用:7.1
4. 若进行多优先级排序,低优先级的排序先进行(允许被高优先级打乱):7.2
5. 最坏时间为线性的选择算法:确保分治有确定的相对平衡划分:8.2
6. 动态规划
1. 找出最优解的性质,并刻画其最优子结构特征;
2. 递归地定义最优值(写出动态规划方程,类似分治法子问题和原问题的关系式);
3. 以自底向上的方式计算出最优值;通常将子问题所做的选择存在一个表中
4. 根据计算最优值时记录的信息,构造最优解。
7. 贪心算法设计和证明思路
1. 活动选择 Th16.1的启示:先想想证明的时候,如果按用来进行贪心选择的性质( 如结束时
间最早)去替换,怎么才能保持正确性不变呢
2. 贪 心算法的最优性证明:把 贪心解与任 一最优解相比较,如果这两个解不同,就去找开始
不同的第一个xi,然后设 法用贪心解的xi去代换最优解的xi,并证明最优解在分量代换之 后
其总价值保持不变,反复进行下去,直到新产生的最优解与贪心解完全 一样,从而证明了
贪心解是最优解。
8. 最优子结构性质和贪心选择性质的区别:
最优子结构性质:设X= (x1 , x2 , x3 , x4 )是问题钱数为A的最优解,则X‘ = (0, x2 , x3
, x4 )是子问题钱数为A - d1*x1的最优解。
贪心选择性质:设X= (x1 , x2 , x3 , x4 )是贪心解 , Y=(y1 , y 2 , y3 , y 4 )是最优解。则
X= Y.
9. 摊还分析不同于平均情况分析,它并不涉及概率,它可以保证最坏情况下每个操作的平均性能
1 Introduction (ch1)
算法的作用
2 Getting Start (ch2,no slides)
无
3 Growth of Functions (ch3, no slides; summation methods)
猜测法(修正细节)、迭代和递归树
Master定理