by 等流星的牧羊人
写完这个这学期大概不用写了。。。。
考点
主要考到前四章，贪心证明为止(两种，数学归纳与。。。。) 看一下课后题
一些例题
估计函数的阶
注：根号n比logn阶高！
递推方程求解
定义
迭代法求解
迭代法求解递推方程
• 直接迭代，代入初值，然后求和
• 对递推方程和初值进行换元，然后求和，求和后进行相反换元，得到原始递推方程的解
• 验证方法—— 数学归纳法
换元
差消法化简高阶递推方程
对于高阶递推方程先要用差消法化简为一阶方程，然后再迭代求解
递归树
递归树是迭代的图形表述
主定理
求和技术
分治策略
动态规划
贪心
数学归纳法证明活动选择正确性
最优装载问题正确性证明
交换论证证明最优调度正确性
贪心法正确性证明方法：交换论证
- 分析算法解与一般最优解的区别,找到把一般解改造成算法解的一系列操作( 替换成份、交换次序)
- 证明操作步数有限
- 证明每步操作后的得到解仍旧保持最优
回溯
线性规划
最大流
Ford-Fulkerson 方法
