分治算法总体思想:
1.将要求解的较大规模的问题分割成多个更小规模的子问题。
2.对这些子问题分别求解。
3.将求出的小规模的问题的解合并为一个更大
规模的问题的解，自底向上逐步求出原来问题的解。
分治法的适用条件:
1.该问题的规模缩小到一定的程度就可以容易地解决；
2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
3.利用该问题分解出的子问题的解可以合并为该问题的解；
4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
大整数乘法:
XY=ac2^n+（（a-c）（b-d）+ac+bd）2^n/2+bd
Strassen矩阵乘法
使用动态规划方法的基本条件:
–最优子结构
•当一个问题的优化解包含了子问题的优化解时,我们说这
个问题具有优化子结构
•缩小子问题的集合,只要哪些优化问题包含了优化子问题,
降低实现复杂性
–重叠子问题
•在问题的求解过程中,很多子问题的解被多次重复使用
–无后效性
•即一个问题被划分阶段后，阶段I中的状态只能由i+1中
的状态通过状态转移方程得来，与其他状态没有关系，
特别是与未发生的状态没有关系
动态规划法的求解步骤:
•找出最优解的性质，并刻划其结构特征。
•递归地定义最优值。
•以自底向上的方式计算出最优值。
•根据计算最优值时得到的信息，构造最优解
矩阵连乘:
最长公共子序列:
设序列X=和Y=的最长公共子序列是Z=
如果xm=yn
zk=xm=yn
是和的最长公共子序列
如果xmyn且zkxm
是和的最长公共子序列
如果xmyn且zkyn
是和的最长公共子序列
凸多边形的最优三角剖分:
0-1背包问题:
贪心法适合的问题：
它有n个输入，而他的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。
显然，可行解一般来说是不唯一的。
那些使目标函数取极值的可行解，成为最优解。
Greedy算法的处理流程
•1、读入一个问题•2、进行贪心排序•3、处理问题•4、综合结果并输出
Greedy算法产生优化解的条件:
贪心选择性质和最优子结构性质
贪心与动态规划法的比较:
动态规划：
每一步作一个选择——依赖于子问题的解。
Greedy方法：
每一步作一个选择——不依赖于子问题的解。
动态规划方法可用的条件
①优化子结构
②子问题相交性
③子问题空间小
Greedy方法可用的条件
①优化子结构
②Greedy选择性
Greedy算法正确性证明方法:
①证明算法所求解的问题具有优化子结构；
②证明算法所求解的问题具有Greedy选择性；
③算法按照②中的Greedy选择性进行局部优化选择
回溯法的解题步骤:
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常见的两种分支限界法:
（1）队列式（FIFO/LIFO）分支限界法按照队列先进先出（FIFO）或后进先出（LIFO）原则选取下一个结点为扩展结点。
（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。
分支限界法与回溯法的对比:
证明题:
凸多边形最优三角剖分:
最优子结构性质
证明：
若凸（n+1）边形P={v0,v1,…,vn-1}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：
三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。
可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。
因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。
0-1背包问题:
0-1背包问题具有最优子结构性质
活动选择问题
引理.1.设S={1,2,…,n}是n个活动集合，[si，fi]是活动的起始终止时间，且f1<=f2<=…<=fn，S的活动选择问题的某个优化解包括活动1.
证.设A是一个优化解，按结束时间排序A中活动，设其第一个活动为k，第二个活动为j.如果k=1，引理成立.如果k≠1，令B=A-{k}∪{1},由于A中活动相容，且f1<=fk,B中活动相容。
因为|B|=|A|,所以B是一个优化解，且包括活动1.
引理.2.（说明活动选择问题具有优化子结构）设S={1,2,…,n}是n个活动集合，[si，fi]是活动i的起始终止时间，且f1<=f2<=…<=fn，设A是S的调度问题的一个优化解且包括活动1，则A’=A-{1}是S’={i∈S|si≥f1}的调度问题的优化解.
证.显然，A’中的活动是相容的。
我们仅需要证明A’是最大的。
设不然，存在一个S’的活动选择问题的优化解B’，|B’|>|A’|。
令B={1}∪B’.对于i∈S’,si≥f1,B中活动相容。
B是S的一个解。
由于|A|=|A’|+1,|B|=|B’|+1>|A’|+1=|A|，与A最大矛盾。
引理.3.（Greedy选择性）设S={1,2,….,n}是n个活动集合，f0=0,li是Si={j∈S|sj≥fi-1}中具有最小结束时间fli的活动.设A是S的包含活动1的优化解,其中f1≤…≤fn，则
证.对|A|作归纳法.1、当|A|=1时,由引理1，命题成立.2、设|A|当|A|=k时,由引理2，A={1}∪A1,A1是S2={j∈S|sj=f1}的优化解.3、由归纳假设，
哈弗曼编码:
引理1（优化子结构）设T是字母表C的优化前缀树，∨c∈C,f（c）是c在文件中出现的频率。
设x、y是T中任意两个相邻叶结点，z是它们的父结点，则z作为频率为f（z）=f（x）+f（y）的字符，T’=T-{x,y}表示了字母表C’=C-{x,y}∪{z}的优化前缀编码树。
引理2（Greedy选择性）.设C是字母表，∨c∈C，c具有频率f（c）,x、y是C中具有最少频率的两个字符，则存在一个C的优化前缀树，x与y的编码具有相同长度，且仅在最末一位不同。
证：
设T是一个C的优化前缀树，且b和c是具有最大深度的两个字符:
不失一般性，设f（b）≤f（c）,f（x）≤f（y）.因x与y是具有最低频率的字符,f（b）≥f（x）,f（c）≥f（y）。
从T构造T’，交换T的b和x；从T’构造T’’，交换T的y和c；往证T’’是最大前缀树
定理.Huffman算法产生一个优化前缀编码树。
证：
由于引理1、引理2成立,而且Huffman算法按照引理1的Greedy选择性确定的规则进行局部优化选择，所以Huffman算法产生一个优化前缀编码树。
单源最短路径问题:
贪心选择性质
贪心选择:
是从V-S中选择具有最短路径的顶点u,从而确定从源到u的最短路径长度dist[u]。
假设如果存在一条从源到u且长度比dist[u]更短的路，设这条路初次走出S之外到达的顶点为x∈V-S，然后徘徊于S内外若干次，最后离开S到达u。
在这条路径上，分别记d（v,x）、d（x,u）和d（v,u）为顶点v到顶点x，顶点x到顶点u，顶点v到顶点u的路长，那么，我们有：
dist[x]≤d（v,x）,d（v,x）+d（x,u）=d（v,u）根据greedy选择方法，如果dist[x]因此，不可能存在在S之外的这个点x。
算法题:
Hanoi塔问题
voidhanoi（intn,inta,intb,intc）
{
if（n>0）
{
hanoi（n-1,a,c,b）;
move（a,b）;
hanoi（n-1,c,b,a）;
}
}
二分搜索:
复杂性为O（logn）
算法：
BINARYSEARCH
输入：
n个元素的升序数组A[1…n]和元素x.
输出：
如果x=A[j]，1<=j<=n，则输出j，否则输出0。
1.low=1;high=n;j=0
2.While（low≤high）and（j=0）
3.
4.ifx=A[mid]thenj=mid
5.elseifx6.elselow=mid+1
7.endwhile
8.returnj
大整数乘法:
复杂度分析:
T（n）=O（nlog3）=O（n^1.59）
算法：
MULT
输入：
2个小于2n的二进制整数X,Y
输出：
为X和Y的乘积XY
1.S=SIGN（X）*SIGN（Y）；
2.X:
=ABS（X）；Y:
=ABS（Y）；
3.ifn=lthen
4.if（X=1）and（Y=1）thenreturn（S）
5.elsereturn（0）
6.else{A:
=X的左边n/2位；
7.B:
=X的右边n/2位；
8.C:
=Y的左边n/2位；
9.D:
=Y的右边n/2位；
10.m1:
=MULT（A，C，n/2）；
11.m2:
=MULT（A-B,D-C，n/2）；
12.m3:
=MULT（B，D，n/2）；
13.S:
=S*（m1*2n+（m1+m2+m3）*2n/2+m3）；
14.return（S）
合并排序:
T（n）=O（nlogn）
算法：
MERGESORT
输入：
n个元素的数组a[1…n]
输出：
按照非降序排列的数组a[1…n]
MergeSort（Typea[],intleft,intright）
if（leftinti=（left+right）/2;//取中点
mergeSort（a,left,i）;
mergeSort（a,i+1,right）;
merge（a,b,left,i,right）;//合并到数组b
copy（a,b,left,right）;//复制回数组a
}
快速排序:
Tmax（n）=O（n2）Tmin（n）=O（nlogn）
voidQuickSort（Typea[],intp,intr）
{
if（pintq=Partition（a,p,r）;
QuickSort（a,p,q-1）;//对左半段排序
QuickSort（a,q+1,r）;//对右半段排序
}
}
intPartition（Typea[],intp,intr）
{
inti=p,j=r+1;
Typex=a[p];
//将//将>x的元素交换到右边区域
while（true）{
while（a[++i]while（a[--j]>x）;
if（i>=j）break;
Swap（a[i],a[j]）;
}
a[p]=a[j];
a[j]=x;
returnj;
}
线性时间选择:
O（n）
template
TypeRandomizedSelect（Typea[],intp,intr,intk）
{
if（p==r）returna[p];
inti=RandomizedPartition（a,p,r）,
j=i-p+1;
if（k<=j）returnRandomizedSelect（a,p,i,k）;
elsereturnRandomizedSelect（a,i+1,r,k-j）;
}
活动选择:
O（n）
算法：
（设f1≤f2≤…≤fn已排序）
voidGreedySelector（intn,Types[],Typef[],boolA[]）
{
A[1]=true;
intj=1;
for（inti=2;i<=n;i++）{
if（s[i]>=f[j]）{A[i]=true;j=i;}
elseA[i]=false;
}
}
Huffman编码:
T（n）=0（n）+0（nlogn）
Huffman（C，F）（使用堆操作实现）
1.n←|C|；
2.Q←C;/*用BUILD-HEAP建立堆*/
3.fori＝1ton-1do
4.z←Allocate-Node（）;
5.x←left[z]←Extract-MIN（Q）;/*堆操作*/
6.y←right[E]←Extract-MIN（Q）;/*堆操作*/
7.f（z）←f（x）+f（y）;
8.insert（Q,z）;/*堆操作*/
9.ReturnExtract-MIN（Q）.
升级会员 