算法基础笔记整理

第1页共10页算法重点总结一、引言——算法基本概念1.什么是算法：有限指令序列，对某个问题能够得出正确答案的规则集合2.算法的特点：确定性，可终止性，可行性，输入，输出3.算法规模：问题实例的大小，输入的大小4.基本运算：主要的、关键的、耗时的最小操作5.算法正确性及复杂度证明方法：反证法、数学归纳法（p(a)成立，且对每个na，只要p(n-1)成立，p(n)一定成立）6.算法分析标准：正确性、工作量、占用空间量：算法运行过程中的内存占用情况、简单性和清晰性、最优性（即算法的上界（工作量的上界）等于求解问题的下界（问题固有的复杂度））7.算法选择方法：经验法和理论法（常用）8.算法的时间复杂度表示方法：大O表示上界，Ω表示下界，Θ表示同阶9.选择排序：每次选择序列中最小值放在有序序列尾部（与无序数列头部元素交换）10.插入排序：将当前元素与前向有序数列比较，查找插入位置，移动后插入二、贪心算法1.贪心算法的一般特性1)优化问题：建立候选对象集2)建立对象集合：划分解对象集和抛弃对象集3)求解终止函数：判断解对象集是否是问题的解或者求解是否结束（未必是最优解）4)可行解函数：判断候选对象集元素是否可以加入到当前解的对象集中（未必是最优解）5)选择函数：指出哪个剩余的候选对象最有可能构成问题的解6)目标函数：给出问题的解2.贪心算法求解模版functiongreedy(C:set):set构造候选对象集S=Φ创建解对象集whileCΦandnotsolution(S)do循环构造解对象集x=select(C)选取C=C\{x}去除iffeasible(S∪{x})thenS=S∪{x}可否加入？ifsolution(S)thenreturnS输出解elsereturn“Nosolution”未找到解3.找零问题的一般特性（1）找最少硬币数，候选对象集{100,25,10,5,1}（2）一选到的硬币集和未被选的硬币集（3）判断解函数（solution）,检查目前已选的硬币集中的金额是否等于要找的钱数（4）如果集合中硬币钱数不超过应找金额，则该集合是可行的（5）选择函数（selection）,从未选硬币集合中找一个面值最大的硬币第2页共10页（6）目标函数（object）：计算硬币金额4.图：最小生成树算法的一般特性1)优化问题：建立候选图的边集2)建立集合：已选中的边集MST，未选边集E-MST3)求解终止函数：如果MST构成生成树，则它是一个解4)解存在函数：候选边加入MST构不成回路，则该边可以加入MST5)选择函数：prim算法选择U和V-U之间的最小边加入MST；KrusKal算法从未选边中选最小边加入MST6)目标函数：计算MST中边权值和5.Kruskal算法思想（1）将所有边按权由小到大排列；（2）MST置空；（3）依次取最小边（u,v）：*若（u,v）加入MST不构成回路则将（u,v）加入MST;*若MST中的边达到n-1条，则结束；Kruskal算法证明：归纳G的边数归纳基础：当G只有一条边，显然G就是最小生成树；归纳假设：设T中有sn-1条边时，T是有希望成为最有解的。当向T中再加一条最小边（u,v）时，且进入后不会使T构成回路。原T中有若干联通分量，加入（u,v）后，减少一个。所以加入后T仍然是有希望成为最有解的。所以算法结束后，T中有n-1条边，构成了生成树，且为最优。6.Prim算法思想（1）解集合T为空，B为任意顶点（2）从B和V-B之间的边中选一最小边(u,v),u属于B,v属于V-B（3）将(u,v)加入T,将v加入B（4）重复(2)-(3)n-1次Prim算法证明：归纳于T中边的数目，如果T在任何步骤都是有希望的，则往T里加一条边后，仍然是有希望的。7.图：单源最短路径（非负边）Dijkstra算法O(n2)FunctionDijkstra(L[1..n,1..n]):array[2..n]arrayD[2..n]C={2,3,…,n}fori=2tondoD[i]=L[1,i]fori=2tondov=someelementofCminimizingD[v]C=C\{v}foreachw∈CdoD[w]=min{D[w],D[v]+L[v,w]}returnDDijkstra算法证明：（数学归纳法）(a)如果一个顶点i满足i1，且i在S中，则D[i]给出了从源到i的最短路径长度。第3页共10页(b)一个顶点i不在S中，则D[i]给出了从源到i的最短特殊路径长度。（i的前驱在S中）8.贪心算法背包问题（可分割）Functionknapsack(w[1..n],v[1..n]):array[1..n]fori=1tondox[i]=0weight=0;whileweightWdoi=thebestremainingobject{seletion}ifweight+w[i]=Wthenx[i]=1weight=weight+w[i]elsex[i]=(W-weight)/w[i]weight=Wreturnx如果根据v/w（价重比）降序顺序选择物品，则knapsack算法可以找到最优解9贪心算法删数问题算法思想：利用数组（优化问题），输入数字序列组成待选集合，用初始输入数字序列作为解集合和初始抛弃集合为空（建立对象集合）。循环中，每次从解集合中去除一个数加入到抛弃集合中（可行解函数），使得解集合数列最大（选择函数），循环结束（求解终止函数）后所得解集合为所求最大值（目标函数）。选择函数：从高位向低位，比较相邻两位数字大小，若高位比低位数字大，则将高位加入到抛弃集合中，若高位比低位小，则向低位移动继续比较。10贪心算法会场安排问题算法思想：利用数组（优化问题），记录活动开始时间和结束时间，按结束时间排序建立待选集合，初始解集合为空（建立对象集合）。循环中，从待选集合中选择结束时间较早的活动，令其与解集合最后一项活动比较两者是否相容（待选会议开始时间大于解集合中会议结束时间），若两者相容，则将待选会议加入到解集合中，若不相容，抛弃当前待选会议，从待选集合中选择下一项。三、分治算法（递归分治算法）1.分治算法的一般三要素：（1）定义一个最小规模的问题，并给出其解（2）把复杂的问题划分为同类型的若干规模较小的子问题，并分别解决子问题（3）把各子问题的解组合起来，即可得到原问题的解2.分治算法模版：FunctionDC(x)ifx=最小问题规模thenreturnadhoc(x)定义最小规模子问题splitexintosmallsub_problemsx1...xk分割原问题成k个子问题fori=1tokdoyi=DC(xi)递归求解子问题combinedy1..ykintoythatissolutionofx组合子问题的解returny得到原问题的解第4页共10页3.二分递归查找算法：functionbinSearch(T[1..n],x)ifn=0orxT[n]thenreturn0elsereturnbinRec(T[1..n],x)FunctionbinRec(T[i..j],x)ifijthenreturn0k=(i+j)/2ifx=T[k]thenreturnkelseifxT[k]thenreturnbinRec(T[i..k-1],x)elsereturnbinRec(T[k+1..j],x)4.分治算法归并排序算法：算法思想：比较两个有序数列首部，取较小值放入解集合，并删除其在原数列中的数据。若某一数列为空，则依次取非空数列元素加入解集合即可。若两个数列无序，则将两个无序数列递归分割，最终得到两个只有一个元素的数列（即为有序），对其进行归并操作。Proceduremerge(U,V,T)i=j=1U[m+1]=V[n+1]=∞{哨兵}fork=1tom+ndoifU[i]V[j]thenT[k]=U[i];i=i+1elseT[k]=V[j];j=j+1设置哨兵拍，避免每次检查数列是否为空ProceduremergeSort(T)ifn足够小theninsert(T)elseU[1..[n/2]]=T[1..[n/2]];V[1..[n/2]]=T[1+[n/2]..n]mergeSort(U[1..[n/2]])mergeSort(V[1..[n/2]])merge(U,V,T){直接插入算法}5.分治算法快速排序算法：算法思想：1．先从数列中取出一个数作为基准数。2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。3．再对左右区间重复第二步，直到各区间只有一个数。Procedurepivot(T[i..j],varL)p=T[i]k=i;L=j+1;repeatk=k+1untilT[k]pork=jrepeatL=L-1untilT[k]=pwhilekLdoswap(T[k],T[L])第5页共10页repeatk=k+1untilT[k]pRepeatL=L-1untilT[k]=pProcedurequickSort(T[i..j])ifj-i足够小insert(T[i..j])elsepivot(T[i..j],l)quickSort(T[i..l-1])quickSort(T[l+1..j])6.分治法求幂算法：算法思想：1．最简单问题：n=0，解是12.问题分解：an=an-1*a3.解的合成：an=an-1*aProcedurepower(a,n):integerifn=0thenreturn1returna*power(a,n-1)四、动态规划算法1.动态算法基本思想：用表记录已解决子问题的答案，需要时再找出已求得的答案，避免重复计算，即用空间换取时间，提高解题效率。2.动态规划设计方法：（1）基于递归算法设计动态规划算法：递归算法对分解的每个子问题都要递归求解，其中可能有许多子问题重复计算，导致效率低下。为避免这种重复，可以将递归算法改写为动态规划算法；（2）基于问题结构设计；3.动态规划的基本步骤：（1）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一个最优解。（该步骤是求最优解的必须步骤）4.最优性原则（principleofoptimality）：构造最优解所面临的子问题解都是最优的。解决一个问题的过程中，需要依次作出n个决策D1,D2,…Dn,若这个决策序列是最优的，对于任何一个整数k，1kn，不论前面k个决策是怎样的，以后的最优决策只取决于前面的决策，即前k个是最优的，则k+1也是最优的。5.动态规划算法的两个特性：（1）最优子性质：最优解只依赖于子问题的最优解；（2）递归结构。6.动态规划背包问题：算法思想：建立二维数组m[n][c]，m[i][j]表示在面对物品i时，背包容量为j的情况下所能获得的最大价值。若容量j小于物品重量w[i]时，不拿取物品，于是m[i][j]=m[i-1][j]；若容量j大于物品重量w[i]时，则第6页共10页考虑拿不拿物品i，比较拿i与不拿i的收益价值，m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i])。依次规则建立二维数组m[n][c]，便可得到背包可装最大价值。if(j=w[i])m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);elsem[i][j]=m[i-1][j];7.矩阵乘法链（1）最优解结构：将矩阵Ai乘到Aj简记为A[i:j](1=i=j=n)，其最少数乘次数为m[i][j]，原问题的最优值为m[1][n]（即矩阵链不需要断开），当i=j时（只有一个矩阵），m[i][j]=0；（2）递归定义最优值：当i=j时，m[i][j]=0；当ij时，若计算A[i:j]的最优次序在k和k+1之间断开，则有m[i][j]=min{m[i][k]+m[k+1][j]+pi-1*p