1.
没东西
2.引言
算法：确定性，能行性，输入，输出，有穷性。
O，Θ，Ω：
O：上界：从某个值之后都大于
Ω：下界：从某个值之后都小于
Θ：上界和下界中间值。
3.递归
4.分治
- 一般方法（DANDC）
分割，治理，合并。
SMALL：规模合适？直接求解：继续分
DIVIDE：分割。
COMBINE合并。
时间：自己推吧
- 二分查找
1-n => 1- mid-1, mid -mid , mid +1 - n 复杂度：logn，两种写法？（递归，循环）
binart search tree:
还有三分。
- 归并排序
先分到1，然后合并的时候治理。把后半段和前半段交错着放进数组。
比较为基础时间下界：nlogn。
- 矩阵乘法
n *n矩阵乘法 => 七个子(n/2 * n/2）矩阵的乘法
- 二维极大点（极大点：没有被支配（存在x比他小，y比他小的点））
先（按x或者y）排序，分。对子集=1：本身就是极大点。‘
合并：如果左边/右边子集的极大点，如果yL < yR，丢弃点L
- 主定理....?感觉不需要记住？
5.贪心
- 一般方法
局部最优组成全局最优。
SELECT：选择当前最优
FEASIBLE：当前最优可否加入解？
UNION：添加到解。
- 分数背包（p，价值，w，重量）
pi/wi 从大到小，然后能取完就取完，不能取完就取部分。
证明：
- 作业调度
就是接水吧。n个作业，有截止时间和收益。找到最大收益的做法。
（收益）排序。尽可能靠后地解决收益小的问题。
证明。。TODO（）
可行调度证明：TODO（）
基于插入的贪心算法？
收益排序，维护截止时间递增序列。
集合树。并查集。维护当前时间（以及之前 ）是否
- 最小生成树
kruskal =》 图变树。
从一个点开始，他的下一个点如果不在树中，扩张这条边。
- 货郎担...?
经过所有城市一次的最短路。对每个点选择最短的边？不能找到最优解！！
6.动规
- 一般方法TODO：最优性原理证明。
多段决策，最优性原理
- 多段图
最短路？分阶段最短路。
（向前递推）COST(i,j)表示从Vi中点j到终点t的最短路径。
COST(i,j)=min{c(j,l)+COST(i+1,l)},l是下一个阶段的点。
（向后递推）COST(i,j)表示从起点s到Vi中点j的最短路径（嗯所以是一样的东西。）
COST(i,j)=min{c(l,j)+COST(i-1,l)},l是上一个阶段的点。
- 货郎担问题
找到图中一条路径（环），恰好经过每个点一次，且长度最短。
g(i,S)表示，从节点i开始，通过S中所有节点，到达节点1的最短路径长度。
g(1,V-{1})是结论。
g(1,V-{1})=min(c(1,k)+g(k,V-{1,k}))。于是有递推式子。
g(i,空)=ci1
g(i,S)=min(c(1,k)+g(i,S-{k}))
复杂度：n^2* 2^n
- 01背包
维护在前i个物品中，重量为j的情况下能获得的最大价值。时间复杂度（O（nm），空间同样）
F(i,j)=max(F(i-1,j),F(i-1,j-w)+p)
状态压缩。为O（W）只需要保存当前行和上一行的数据。
序偶对法
维护（背包价值，背包重量）的列表。去重，取最大价值且重量为M的二元组。（状态最多2^N)种，可以通过筛选（合法化，去重）减少。时间复杂度（在每次状态扩张时都会翻倍！呜呜呜呜呜可恶啊）
- 可靠性设计
在最大成本c下，流水线的可靠性最大化。流水线中，每种设备最少一台，有成本限制。0n背包。
- 最优二分检索树（复杂度On^3）
左子树/右子树分别大于，小于父节点。
最优二分检索树：最小化查询次数。TODO
- 矩阵链乘积：TODO
7.回溯
需要求组合，并且需要回顾先前情况。多米诺性质：在得到某个状态不成立后，后面的情况都可以不考虑了。（剪枝）
扩展节点
- 子集和
给出n个整数和M。要找出所有子集，其和为M。
可以转成？固定长元组表示（xi）xi = 0或1，解空间：2^n。（换种表达是，求出一个解向量和原始向量的点乘为M）。
约束函数：大于M不考虑。
- n皇后。。。
满足任意两个皇后不存在在（同一行，同一列，同一对角线上）
考虑每一行的皇后，可以放在第i行的1-n列。从而，可以进行回溯搜索。约束：行-列不同，行+列不同。可以压缩棋盘到一维。
- 图着色问题
相邻不同色。
8. 分支限制界法
也许算是一种奇怪的剪枝...？
- 一般方法
扩展节点方法不同（回溯变种）
没结束时：对于所有儿子节点，判断约束，满足添加到活结点列表。选取，迭代。（类似BFS的queue？）
如果用的queue做为列表，那么叫FIFO检索。如果用priority queue，LC检索。（优化的dijkstra）
- LC检索
优先级：C最小成本值。（深度？）
- 15-谜问题
十六个格子15个块。移动到有序状态。
- 最小成本
- 作业调度
- 货郎担
9.NP完全？
多项式时间算法是好算法（对比，指数级别）
可以在多项式时间内解决的判定问题是P
可以在多项式时间内用不确定算法验证的判定问题：NP。
所有的P都是NP问题。
NPC问题：所有的NP问题能通过一个多项式时间算法转换为某个NP完全问题。
任何 NP问题都可以在多项式时间内转化为为可满足性问题。可满足性在P内,当且仅当P=NP