「大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页例子）：
划为4等份：
不看有特殊格那份，其它3份取离结合点最近的格子，拉黑，就形成了一块骨牌。
现在每份都有1块特殊格，然后每份再划4等份：
每一小份重新执行上面的算法（递归了），忽视特殊份，拉黑离结合点近的。
然后继续递归，重复刚才的步骤（子问题结构完全相同）。
当然这里棋盘比较小，到这里已经可以看出结果。
递归中止条件：
当子棋盘（划出的小份）只剩下3个普通格时。
七种常用排序算法的时间复杂度：
最好情况O（?
）
平均情况O（?
）
最坏情况O（?
）
稳定性
冒泡
n
n2
n2
稳定
选择
n2
n2
n2
稳定
插入
n
n2
n2
稳定
希尔
n1.3
nlogn~n2
n2
不稳定
堆
nlogn
nlogn
nlogn
不稳定
归并
nlogn
nlogn
nlogn
稳定
快速
nlogn
nlogn
n2
不稳定
其中最坏情况最重要。
稳定性的意思：
假设有一个数组{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个公式哪个得出的结果大，就选哪个。
然后可以构造出一张表：
背包容量为C时，能选择的最大价值。
重量
价值
C=1
C=2
C=3
C=4
C=5
C=6
C=7
C=8
C=9
C=10
A
3斤
4元
A
X
X
4
4
4
4
4
4
4
4
B
4斤
5元
A+B
X
X
4
5
5
5
9
9
9
9
C
5斤
6元
A+B+C
X
X
4
5
6
6
9
10
11
11
解释下，X表示放不下，因为这里最轻的物品也要3斤，C=1或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
0
1
1
3
3
3
A2
0
2
3
3
3
A3
0
3
3
3
A4
0
4
5
A5
0
5
A6
0
所谓断开位置，就是如何加括号（结合律）
原式：
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
A2
A3
A4
A5
A6
A1
0
15750
7875
9375
11875
15125
A2
0
2625
4375
7125
10500
A3
0
750
2500
5375
A4
0
1000
3500
A5
0
5000
A6
0
比如，A3A4A5连乘，就查A3~A5，得2500，表示这3个矩阵连乘，最少元素相乘次数为2500次。
那么，我们最终要的答案当然就是A1~A6，也就是15125，6个矩阵相乘最少15125次，这就是整体最优解。
动态规划法的常规步骤：
1、分析最优解的结构。
2、建立递归关系。
3、计算最优值。
4、构造最优解。
单源最短路径（贪心）：
用的迪杰斯特拉算法。
以书p101页的图为例：
有2个集合：
集合S放已启用的顶点，集合U放未启用的顶点。
具体看例子。
一开始集合S={A}，只有起点。
A->B
A->C
A->D
A->E
最短路径
A->B
还到不了
A->D
A->E
最短路径长度
10
30
100
所在集合
U
U
U
U
查表可知，A的邻点中，到B的距离最短，所以将B加入集合S
S={A,B}
现在A可以到C了：
A->B->C，填进去：
A->B
A->C
A->D
A->E
最短路径
A->B
A->B->C
A->D
A->E
最短路径长度
10
60
30
100
所在集合
S
U
U
U
查表
S={A,B,D}
现在发现，A到其它点的路径选择多了。
比如A到E：
A->E=100
A->D->E=90
显然后一条虽然经过的点多，但总路径短了，于是更新此表：
（A到其它点也是，只要有更短路径就换上去）
A->B
A->C
A->D
A->E
最短路径
A->B
A->D->C
A->D
A->D->E
最短路径长度
10
50
30
90
所在集合
S
U
S
U
查表，在集合U中，选A过去最近的，发现是A->C=50（路径A->D->C）
S={A,B,D,C}
加入C后，继续找A到其它点有没有更短的走法，有的话就更新表
A->B
A->C
A->D
A->E
最短路径
A->B
A->D->C
A->D
A->D->C->E
最短路径长度
10
50
30
60
所在集合
S
S
S
U
到此，集合U中只剩下E，加入S（路径A->D->C->E）：
S={A,B,D,C,E}
最后次更新表（E没有出去的方向，所以实际上本次无更新）
A->B
A->C
A->D
A->E
最短路径
A->B
A->D->C
A->D
A->D->C->E
最短路径长度
10
50
30
60
所在集合
S
S
S
S
最终集合U中元素全部到了S中，表则如上所示。
实际编程中，可以用一个数组表示此表，比如数组arr，arr[2]保存A->B的最短路径长度，arr[3]保存A->C的……以此类推。
最终：
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个。
简言之，先装轻的，再装重的，当然能装的就最多。
注意：
虽然是贪心法，但本题得到的一定是最优解。
动态规划与贪心的关系：
动态规划建表查表需花费时间、空间开销，效率比贪心低，但肯定能获得最优解。
贪心每次只取局部最优解，效率高，但整体不一定（注意是不一定）是最优解。
升级会员 