算法设计与分析期末复习

题型

填空12
选择10
3 4 5 6第2，3，4，5章
分治、dp、贪心、回溯分支界限四道大题，每道大题16-18分
复习重点：
复杂性定义
四个符号：上界、下界：填空题可能给个定义，让你写是哪个渐进符号
渐进上下界性质
重点看阶的定义

递归和分治：

二分搜索、大整数乘法（cue了大整数乘法的时间复杂度）、矩阵乘法、棋盘、合并、快排、线性、最接近点对
循环赛日程肯定不考
题目可能直接问你时间复杂度是多少，不告诉你这个问题是什么
主定理肯定要会（第一次作业第二题，第二次作业有关主定理的内容；第一种情况epsoro要写出来最好）
二分搜索：比较简单的分治法
矩阵乘法时间复杂度
棋盘覆盖：时间复杂度
合并排序：时间复杂度
（第二次作业第三题，逆序对；考试可能会以类似逆序对的形式来考；逆序对nlogn时间的算法【nlogn想到主定理，需要用一个每次把子问题】）
如果考比较难的：快排、线性时间选择，大概率是ppt原题
快排：可能要画排序的表
快排：什么情况下可能会有比较高的时间复杂度；【严重不对称，快排每次分割1个元素和n-1个元素】；平均情况nlogn（不用管平均情况的求解细节）
求最大元（求中位数作业题；第三次第二题）
线性时间选择：找到第k小的元素 时间复杂度O(n)；模仿快排对数组进行递归划分，注意中位数数组的中位数m不一定是整个数组的中位数，但是不会太偏；线性时间选择的时间复杂度不考，应该不考大题；这个复杂度不能用主定理
不能用注定里的情况，要会展开
最接近点对：时间复杂度 存在Onlogn的，这是下界 ；小题里会出现：最接近点对用什么策略？扫描最多扫6个点

建议仔细看看：合并 快排 线性时间选择

DP：DP的两个性质（最优子结构，重叠子问题）

矩阵连乘问题：状态转移方程；打表，求出m[1][n],s矩阵确定加括号方式；时间复杂度On^3（普通算法和好的算法可能都要考）
考试可能会给个例子，然后写转移方程，然后写复杂度

最长公共子序列
最大子段和：也可以用分治，时间复杂度nlogn
作业里的最大m子段和；
最大子矩阵和跳过，不考
凸多边形最优三角剖分
流水作业调度：johnson不等式烤得比较多，怎么写的，什么情况下满足，什么情况下不满足；流水作业调度的Johnson算法
0-1背包问题：dp，分支限界，回溯法都可能会有
0-1背包问题：xi，vi，求和式子之类的（问题的数学描述）；

可能dp会有一些扩展
作业：编辑距离之前考过
可以参考：交换硬币游戏：如果有两个：取最大，如果有三个：拿完第一个以后，剩下的人取剩下的两个的最大的【我拿到的：拿一个+剩下里小的】;复杂度：n^2

贪心（这章不考原题，应该是变）

活动安排、最优装载、哈夫曼、最小生成树、多级调度
可能会考：写一个策略，证明它是最优策略
一般背包策略
例子：活动安排问题的证明：分两步：第一步替换；如果有个不是最优解的，把它替换就是最优解？？？？
多机调度也可以看一下
如何证明贪心是最优的

自总结

贪心选择性：每一步贪心选出来的一定是原问题的最优解的一部分
最优子结构：每一步贪心选完后会留下子问题，子问题的最优解和贪心选出来的解可以凑成原问题的最优解
贪心策略：对于每次都选择最小的，可以使用类似哈夫曼树的证明方法，贪心选择性质：如果存在一个最优编码，但是没有选择频率最小的两个字符，互换，证明选择最小的一定可以获得最优答案，从而，每次选择最小的都能获得最优答案；再证明最优子结构性质：首先要找到子问题和解的关系，接着假设子问题不是最优，推导出解不是最优，与解最优矛盾。
把每一步贪心选择的结果写出来，看看有什么规律，然后用数学归纳法证明

回溯法

子集树、排列树
对某个问题，它的解空间是子集树还是排列树？选择或者填空
n后问题：排列树
概念：扩展结点，活结点，死结点的概念
回溯法基本思想：DFS，开始的时候根节点是活结点也是当前的扩展结点
考试会考填空题，填代码里的特殊条件e.g.装载问题：剪枝、更新r、记录r【1：40:00左右，音频】
了解每个问题都是怎么做的；限界函数怎么写
n皇后可以不看
0-1背包回溯可以看一看
最大团问题：右子树，限界判断
m着色可以不看

分支限界

布线问题（课本和ppt做法不一样；终点往前搜；起点忘后搜），单源点最短路径，批处理作业调度
旅行售货员补考、6.7 6.8删掉，其他都看看
分支限界法和回溯法的区别：多次成为扩展结点（回溯），一次成为扩展结点（分支限界）
优先队列，确定优先队列的选取

装载问题为例：不管如何，右儿子一定可行（不会超过c）；剪枝智能剪掉右子树，因为右子树每次都是进入的【右子树剪枝，提前更新bestw（当前位置的bestw并非是最终的bestw），提前做剪枝】【不同：回溯法的限界函数是在叶子里获得的，但是分支限界法是在中间获得的，需要提前更新剪枝的参照】
每一步队列变化的方式，要会写，每一层的bestw要会计算（装载问题ppt里有）

如何定义优先级？
优先队列：优先级最大的会成为下一个扩展结点；结点按照优先级排序，不知道搜到哪一层，对于装载问题，标注一下结点在那一层，用数组把r存起来，对于每一层来说，剩余装在重量是固定的

布线问题：定义方向和边界，边界设置围墙，每一步做一些检查

最大团：约束，右儿子：判断un（当前可能最优解）是不是大于bestn【un=cn+(n-i)】

批处理作业调度，没讲就不考，没讲的都不考
6.7 6.8 6.9都不考

第五章、第六章算法框架+关键的点
贪心：不会给特别复杂的贪心，把贪心策略找出来就好；怎么找怎么证明；贪心策略写出来
dp：稍微有些变化;定义子问题，动态转移方程，时间复杂度
分治：
考试题目大部分都是上课讲的，除了dp
dp可能思路是类似的
P，NP，NPC问题