P问题 - 可以在多项式时间内解决的问题。

NP问题 - 可以猜到答案，并可在多项式时间内验证是否正确的问题。

NPC（完全）问题 - 是NP问题，且其它所有NP问题都可约化到它的问题。

NP-Hard（难）问题 - 不一定是NP问题，但其它所有NP问题都可约化到它的问题。

时间复杂度的概念：

    给定算法的运行时间增长趋势，一般输入规模看成很大。

（渐进）阶从低到高：

    1 < logn < n < nlogn < n2 < n3 < 2n < n! < nn

「大O阶表示法」的计算原则：保留最高阶，去头去尾。

头：最高阶项的系数。

尾：非最高阶项与常数。

比如：

6n3 + 4n2 + 10000 = O( n3 )

        10n2 + 2n = O（2n）

随机化算法分类：

    数值随机化算法

    舍伍德算法 

    拉斯维加斯算法 

    蒙特卡罗算法 

棋盘覆盖（分治策略）：

    前提：棋盘必须正好有2k×2k（k = 自然数）个格子。

    步骤：

1、将棋盘划分成4个子棋盘。

2、除了有特殊格的子棋盘外，其它3个盘里各取离结合点最近的格子，组成骨牌。

3、将每个子棋盘再划分成4个子棋盘，同样执行步骤2。

4、递归终止条件：子棋盘的普通格只剩3个。

    比如一个8×8的棋盘（书p21页例子）：

当然这里棋盘比较小，到这里已经可以看出结果。

递归中止条件：当子棋盘（划出的小份）只剩下3个普通格时。

七种常用排序算法的时间复杂度：

稳定性的意思：

假设有一个数组{ 2, 5, 2, 7, 1 }

其中第一个2假设叫a元素，第二个2叫b元素吧。

对其排序后得{ 1, 2, 2, 5, 7 }

原本a在b前面，如果排序后，a还在b前面，就是稳定的。它们调换了就是不稳定的。

也就是说稳定性，决定了同值元素的顺序会不会变动。

理论上，希尔和堆排序不会考，因为上课没讲过。

0-1背包（动态规划）：

假设有3个物品：

物品A重3斤，价值4元；

物品A重4斤，价值5元；

物品A重5斤，价值6元。

    考虑方式：

当放了n-1个物品时，第n个物品放还是不放？

    设：

C - 当前背包容量（斤）

w[n] - 第n个物品的重量（斤）

v[n] - 第n个物品的价值（元）。

F( n, C ) - 将前n个物品放入容量为C的背包时，能获取的总价值。

    如果不放第n个物品：

公式： F( n-1, C )

如果放第n个物品

公式： F( n-1, C - w[n] ) + v[n] 

    简单来说，就是把C、w[n]、v[n] 代入公式，看2个公式哪个得出的结果大，就选哪个。

    然后可以构造出一张表：

    关键是后面绿色的值是怎么得到的，它是一行行构造出来的。

    A行表示只有物品A时，怎么放能得到最大价值。

    A + B行表示只有A与B时，怎么放能得到最大价值。

    A + B + C行表示有ABC时，怎么放能得到最大价值。

    先看A行，因为就物品A，也没有什么比较公式，很显然C大于3时就可以放进A，因为每种物品就一个，所以不管背包多大，最大价值都是4元。

    再看A + B行，从这行开始可以套公式了。

比如C=3时：

F( n-1, C )： 就是A行C=3时的价值，也就是4元。

F( n-1, C - w[n] ) + v[n]： C-w[n] = 3 - 4 = -1 ，显然4斤的B根本放不进3斤的包。

所以最大价值是4元

再比如C=8时，

    F( n-1, C )： 还是4元。

    F( n-1, C-w[n] ) + v[n]： C-w[n] = 8 - 4 = 4，F( n-1, 4 )，也就是A行的C=4，为4，再加上v[n]=5，最终结果是9元。

    最大价值选大的，9元。

再看A + B + C行，一样的，就举C=9时的例子吧：

    F( n-1, C )： A + B放在C=9，查表得9元。

    F( n-1, C-w[n] ) + v[n]： F( A+B, 9-5 ) + 6 = 11元。

    选大的，11元。

最终整表的右下角那个，就是整道题的最优解，即11元。

所谓动态规划，就是在算法中，逐步建立起这张表。填表过程中，后面的值可能会依赖前面的值，这时只要去查表就行了，而不用去临时计算。换言之，不做重复的子计算。这种算法效率高了，但存表需要空间，典型的空间换时间的做法。

矩阵连乘（动态规划）：

    矩阵连乘怎么算不重要，这里不写了。

关键3点：

1、相乘的矩阵，前面一个的列数要与后面一个的行数相等。

比如3行5列与5行2列的可以乘。

而3行5列与4行2列的没法乘。

2、a行b列与b行c列相乘，会得到一个a行c列的矩阵。

3、a行b列与b行c列相乘，元素相乘次数 = a×b×c（次）。

换言之，假设有不同的矩阵A、B、C。

那么（A×B）×C与A×（B×C），会产生不同的相乘次数。

而这个问题就是要找到，相乘次数最少的顺序。

举例来说，约定A（3, 5）表示一个3行5列的矩阵， 假设有：

A（3, 5）

B（5, 4）

C（4, 7）

如果按（A×B）×C的顺序：

    A×B = （3, 4），相乘次数 = 3×5×4 = 60

    ( 3, 4 )×C，相乘次数 = 3×4×7 = 84

    最终，整个连乘过程中，次数为60+84 = 144（次）

如果按A×（B×C）的顺序：

    B×C = （5, 7），相乘次数 = 5×4×7 = 120

    A×( 5, 7 )×C，相乘次数 = 3×5×7 = 105

    最终，整个连乘过程中，次数为120+105 = 225（次）

显然第一种乘得少，乘得少代表效率高，这就是我们追求的。

算法执行过程中，也会逐步建立2张表（书上p48的（b）和（c）表）

按书上的例子，有6个矩阵A1~A6，最终填表得：

断开位置表：

原式：A1×A2×A3×A4×A5×A6

A1到A6怎么断？查表为3，也就是在A3左边断，得：

（A1×A2×A3）×（A4×A5×A6）

    A1到A3查表为1，得：

（A1×（A2×A3））×（A4×A5×A6）

    A4到A6查表为5，得：

（A1×（A2×A3））×（（A4×A5）×A6）

    于是这就是答案，按这个顺序，元素相乘的次数最少。

    相乘次数表：

    那么，我们最终要的答案当然就是A1~A6，也就是15125，6个矩阵相乘最少15125次，这就是整体最优解。

动态规划法的常规步骤：

1、分析最优解的结构。

2、建立递归关系。

3、计算最优值。

4、构造最优解。

单源最短路径（贪心）：

    用的迪杰斯特拉算法。以书p101页的图为例：

    有2个集合：集合S放已启用的顶点，集合U放未启用的顶点。具体看例子。

一开始集合S = { A } ，只有起点。

S = { A, B }

现在A可以到C了：A -> B -> C，填进去：

S = { A, B, D }

现在发现，A到其它点的路径选择多了。比如A到E：

A -> E = 100

A -> D -> E = 90

显然后一条虽然经过的点多，但总路径短了，于是更新此表：

（A到其它点也是，只要有更短路径就换上去）

S = { A, B, D, C }

加入C后，继续找A到其它点有没有更短的走法，有的话就更新表

S = { A, B, D, C, E }

最后次更新表（E没有出去的方向，所以实际上本次无更新）

最终：

    arr[2] = 10

    arr[3] = 50

    arr[4] = 30

    arr[5] = 60

那么，如果我现在想知道A到C怎么走最短，那么查表（数组）就可知：

走路径A -> D -> C最短，长度为50

可以看到，每次迭代，集合U都往集合S中送一个点。

而考虑上那个点并更新表后，每次都会获得当前最优的解。

当全部迭代完成，最终得到的表就是整体最优解表。

这一点要注意，贪心法解题，很多都只能获得近似解，但迪杰斯特拉算法可以获得最优解。 

将以上步骤抽出来：

1、初始时，集合S只包含源点o，集合U包含除了源点的其它顶点。

2、从U中选取一个距离源点最短的顶点加入S中。

3、以S中现有顶点组成路径，审查o到其它点是否有更短路径，有则更新。

4、重复2、3步。

最优装载（贪心）：

    比如有艘轮船，可以装10吨货物。

假设现在有5件货物，重量分别是3、1、7、4、9吨。

    装最多货物的思路：

1、先对货物按重量从小到大排序：1、3、4、7、9吨。

2、依次装船，直到装不下。这里装上1、3、4后就放不了7了。所以最多装3个。

简言之，先装轻的，再装重的，当然能装的就最多。

注意：虽然是贪心法，但本题得到的一定是最优解。

动态规划与贪心的关系：

    动态规划建表查表需花费时间、空间开销，效率比贪心低，但肯定能获得最优解。

    贪心每次只取局部最优解，效率高，但整体不一定（注意是不一定）是最优解。下载本文