原先一直没注意这一门，大概是因为学这些算法的时候，板子都不知道背多少遍了。可是考试毕竟不一样，如果来个证明很容易抓瞎。
看了往年的试题，可能确实因为难度高，范围一缩再缩，虽然是基本按照算导来的，但是算法基本都是最基础的那种。20年之前网络流也是重点，最小割最大流，现在完全不提了。21年之前一般要出一道模板3SAT规约题，而本学期只是简单一提，完全没讲到具体规约的过程。
总而言之，范围还是挺有限的，不过考虑到课件全英文＋大量证明，想要真掌握还是挺难。
大概有这么几个重点：
1.时间复杂度，上下界。应该会有分析题，但是我一般是靠脑补。注意理论。
五种符号分别是渐进上界O（一般的时间复杂度），上界o，渐进下界Ω，下界ω，以及一个渐进紧确界那个奇怪的符号。
可能涉及到证明，后续各种算法大概率都会出个复杂度的问吧，不过对于一般的算法看循环去猜差不多总能对。
2.递推式的复杂度解析，通常用主定理就行，偶尔可以猜猜，但是不好证明。
三种方式：猜想+数学归纳证明，递归树（也就是模拟每一层分治，分别计算，注意合并的成本），主定理（是从递归树推出来的，证明看过但是实在想不起来了。）
主定理最常用，但是有时候不好合并也需要用递归树。
别忘了三种情况。如果前面大就取前面，一样大就加个log，后面大还需要比较af(n/b)<=cf(n)且c<1,也就是不能越分治花的时间越长，那就没法往下推了。如果满足，则用后面当上界。
logb a是怎么推出来的？考虑递归树逐层往下，一共会有logb(n)层，每层需要分裂a个子问题，那么在满足上述3的条件的情况下，可以忽略非叶子节点造成的损耗（都是log级别的），一共有a^(logb(n))个叶子，每个是O(1),总共就是O(a^logb(n)),变形成O(n^logb(a)).这是递归过程中针对每个子问题的处理的时间复杂度的上界。
但是合并子问题还有一部分成本，也就是后面的这个f(n)存在的意义。然而分割子问题的时候复杂度随着节点增加而提高，对于合并成本来说却在降低，因此有可能永远不会超过顶层的f(n).这也是在2中可以推出f(n)logn的原因，可以想象一个倒金字塔。
3.证明贪心策略，写伪代码。贪心很复杂，但是板子应该就这些，不会很难。
活动选择问题。用剪切-粘贴法证明贪心策略。
证明贪心策略也就是证明贪心选的解在答案中，一般先考察某个子问题的最优解，然后试着换掉一个贪心选择，看答案是否会变小。
4.分治算法，由于快排这种玩意都没讲，分治也不会讲的很多，基本就是算算复杂度，写写思路。
5.dp，不用多说了。不知道背包问题是否需要证明，注意证明最优子结构的方法，也有可能问和贪心策略的区别，举例为啥不能贪啥的老问题。背包的话似乎讲的也不多，就是最基础的01，多重这么几种，更恶心的背包都没涉及。
钢条切割，01背包，分组背包（划掉），多重背包，可以分割的背包（不明白为啥算背包）。
当初说的最优子结构和无后效性在这里概念也有变换。
如何证明最优子结构？一般是反证，假设两个最优的子问题不在最优解里，找到矛盾之处。
证明非常扯，差不多是我看他有他就有的意思。
无后效性——子问题不相关，我想还是前者更好理解。其实就是求解子问题不能改变别的子问题，要不然就会一直优化下去。但是课件没告诉你一些后效性可以用多维优化掉。
6.基础图论，主要是图的一些概念，dfs和bfs。注意链表，难度不会很大。强连通分支求法注意（貌似没讲Tarjan）
V是点，E是边。
图论的证明题可以试着证明一下，一般都不会。
一些概念：连通图，强连通图，子图。完全图：任意两点之间有一条边。
bfs和dfs：bfs里有一些证明题。dfs可能要模拟dfs序。
dfs会形成一棵树，除了树上的变还会有别的边，注意分类。
强连通分量：两遍dfs找，第一次在原图上dfs，记录时间戳，第二次按照时间戳在反向图上dfs，凡是能到的都是。
7.最小生成树，我记得kruskal和prim就讲了一种，忘了是哪个，都看看好了。
事实上都讲了，为了讲kruscal专门说了并查集。
别记反了：krucal是森林，每次找最小边加入，并查集维护。
prim是一颗树，每次找连到这棵树最小的边。不用并查集，用优先队列维护。
次小生成树：只提及朴素算法，暴力拆边替换。回到OI时期或许还能搞个二分答案或者树上倍增？
瓶颈生成树：二分答案。这个难度应该就不会考了吧。
8.单源最短路，只说了Dijkstra，Bellman-ford也说了，其实就是弱化版SPFA。堆优化也没说。大概率是根据图描绘流程。
对于Bellman-ford，注意判断负权回路。课件里仍然用了近乎诡辩的方法证明。
BF需要N-1次循环，如果过了这么多循环仍然可以松弛说明有负权回路，但是实际上也许不到N-1就松弛完了，这时候就可以退出。
这就是为什么SPFA会被卡到N^2!!!!
约束图。额。
网上几乎没资料。看定义应该是源点有到所有点的权值为0的边，且其它各边之间的权值服从约束，要求找可行的解。
你赢了。
9.多源最短路：n次Bellman-ford，floyd-warshell。注意弗洛伊德的变体可能用来求矩阵乘法啥的（可能本来就差不多吧）
一些复杂度。
充分可见我校算法课历史悠久。
10.NP，NP-hard，NPC以及NPC规约问题。只讲了概念，应该不会出规约题，这种难度如果不是明讲大概不太会有人能证。
稍微看看3-sat到独立集吧。
一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。也就是说B的解法能同时解决问题A和问题B，问题A可以约化为问题B。这个示例说明什么呢？A的时间复杂度是≥B的时间复杂度。这样的话，相当于我们用问题B简化了问题A。
祝考试顺利！
