算法概论复习总结

1算法概论复习总结第0章序言1、Fibonacci数列（斐波那契数列）斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0；F1=1；Fn=F(n-1)+F(n-2)（n=2，n∈N*）。2、大O符号无穷大渐近，f=O(g)成立；无穷小渐近，f=Ω(g)成立；比值为1时，f=Θ(g)成立。第1章数字的算法1、因子分解：将一个数字N，分解成多个素数的乘积形式。2、素性测试：判断一个数字N是否为素数。3、最大公因数实现：辗转相除法。while(n!=0){r=m%n；m=n；n=r；}4、模运算：AB(modN)N整除(A-B)例：25313(mod60)，即253mod60，值为13。5、RSA（公钥加密算法）RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。它基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其难。6、MD5（信息—摘要算法）：用于确保信息传输完整一致。7、散列表（哈希表HashTable）：根据关键码值M而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。2第2章分治算法1、核心思想：分，治，和。2、主定理：对于常数a0，b1，d=0，有T(n)=aT(n/b)+O(n^d),则：3、合并排序（归并排序）合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。无序排序的时间复杂度为O(NlogN)有序排序的时间复杂度为O(N)4、排序算法的稳定性在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的。稳定的排序算法有：基数排序、冒泡排序、直接插入排序、折半插入排序、合并排序(归并排序)不稳定的排序算法有：快速排序、希尔排序、堆排序、直接选择排序第3章图的分解1、图的表示：①邻接矩阵有向图和无向图邻接矩阵，用二维数组表示，能够一次到达的点用1表示，不能够一次到达的点用0表示，如果边有权值用权值表示。②邻接表（注意逆邻接表）有向图和无向图邻接表，由顶点域vertex，指针域firstedeg，邻接点域adjvex，链域next四部分组成，最后为符号。log()()(log)()bddddadnabTnnnabnab32、深度优先搜索(无向图，有向图深度优先搜索)其中有向图注意拓扑排序(默认降序)，排序时注意每个顶点的pre和post值，如果遇到需要在多个顶点间进行选择的情况，按照顶点的字母序进行。(其中pre是读取顶点时候的值，post是离开顶点时候的值。)3、有向无环图（DirectedAcyclicGraph）性质：①有向图含有一个环当且仅当深度优先搜索过程中探测到一条回边；②每个有向无环图至少还有一个源点和一个汇点。4、强连通性：一个有向图是强连通的，当且仅当图中有一个回路，它至少包含每个节点一次。第4章图中的路径1、距离：两个顶点之间的距离是指两者之间最短路径的长度。2、广度优先搜索Dijkstra算法即迪杰斯特拉算法，用于解决单元最短路径问题。第5章贪心算法1、基本思想：在解决问题时，总是做出在当前看来是最好的选择。例：最小生成树（MST，MinimumSpanningTree）2、Kruskal算法（克鲁斯卡尔算法）由一个空的图开始，并且不断重复地选择未被选择中的边中权重最轻且不会形成环的一条，即通过逐条增加边来构造最小生成树。3、Prim算法由X定义的子树将生长一条边，具体来说，选择S中顶点与外顶点之间的最轻边加入X，最终边集X构成了一棵树，S是其顶点集合。4、Huffman编码（哈夫曼编码）构造最优二叉树，编码时，左边为0，右边为1。4第6章动态规划（DynamicProgramming）1、有向无环图的最短路径问题dist(j)=min{dist(i1)+d(i1,i),....,dist(ik)+d(ik,i)}其中：d(i,j)是顶点i到j的边上的权值2、背包问题：给定一组物品，每种物品都有自己的价格和重量，在限定的总重量内，做出选择，使得物品的总价格最高。3、旅行商问题（TSP，TravelingSalesmanProblem）旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最短路径成本。基本思路：近邻点法，先从离源点最近的一个需求点开始，此后需找离最后加入路线的点的最近需求点，直到最后。第7章线性规划与归约1、线性规划（LP，LinerProgramming）例：利润最大化、生产计划、最优宽带分配2、网络流求最大流要画出剩余网络图，根据图中实际最大流量求出，上限是始点的和，最大网络流小于或者等于上限。最小分割最大流定理：网络中最大流的规模等于其中(s,t)分割的最小容量。3、二部图匹配如果左边和右边两两配对，并且配对双方总是相互喜欢的，这样的配对称为完美匹配。第8章NP-完全问题（非确定多项式问题）1、分类：P问题，NP问题，NP完全问题，NP难问题其中P为多项式（Pdynomimal）52、可满足性问题（SAT）：一组命题逻辑公式，主要是合取范式，即是否存在其变元的一个取值使得该组范式全部取值为真。3、搜索问题一个搜索问题是由一个算法C描述的，以问题实例I和一个可能的解S为输入，运行在关于|I|的多项式时间内。我们说S是I的一个解，当且仅当C(I，S)=ture。4、欧拉七桥问题基本思想：不重复每条边，进入该点与离开该点的边应该相等，即与该点连接的边为偶数，也就是说该点的度是偶数。而七桥问题中,与每个陆地相连接的桥都是奇数，即每个点的度都是奇数，因此七桥问题无解。第9章NP-完全问题的处理1、回溯算法（Bcaktracking）（深度优先搜索）基本思想：从一条路往前走，能进则进，不能进则退回来，换一条路再试。例：4皇后问题（任意两个皇后都不能处于同一行、同一列或同一斜线上）2、分支定界法（Branch-and-Bound）（广度优先搜索）基本思想：以广度优先搜索方式画出一个树，然后选择最小消耗或者最大效益的一条路线。3、聚类（clustering）K-means算法也称K均值聚类算法，是通过迭代过程把数据集划分为不同的类别，使得评价类聚性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。步骤：①为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心；②将样本集中的样本按照最小距离原则分配到最邻近聚类；③使用每个聚类中的样本均值作为新的聚类中心；④重复步骤二三，直到聚类中心不再变化，这时将得到K个聚类。6附录1、折半查找(二分查找)①非递归算法publicstaticintbinarySearch(int[]srcArray,intdes){intlow=0;inthigh=srcArray.length-1;while(low=high){intmiddle=(low+high)/2;if(des==srcArray[middle]){returnmiddle;}elseif(dessrcArray[middle]){high=middle-1;}else{low=middle+1;}}return-1;}②递归算法intBinSearch2(intr[],intlow,inthigh,intk){if(lowhigh)return0;else{mid(low+high)/2;if(kr[mid])returnBinSearch2(r,low,mid-1,k);elseif(kr[mid])returnBinSearch2(r,mid+1,high,k);elsereturnmid;}}72、冒泡排序算法voidBubbleSort(intr[],intn){exchange=n;while(exchange!=0){bound=exchange;exchange=0;for(j=1;jbound;j++)if(r[j]r[j+1]){r[j]=r[j+1];exchange=j;}}}3、归并排序算法voidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i=m&&j=t){if(r[i]=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}if(i=m)while(i=m)r1[k++]=r[i++];elsewhile(j=t)r1[k++]=r[j++];}84、快速排序算法①快速排序一次划分算法intPartition(intr[],intfirst,intend){i=first;j=end;while(ij){while(ij&&r[i]=r[j])j--;if(ij){r[i]=r[j];i++;}while(ij&&r[i]=r[j])i++;If(ij){r[j]=r[i];j--;}}returni;}②快速排序算法publicvoidquickSort(Integer[]list,intlow,inthigh){if(lowhigh){intmiddle=getMiddle(list,low,high);//将list数组进行一分为二quickSort(list,low,middle-1);//对低字表进行递归排序quickSort(list,middle+1,high);//对高字表进行递归排序}}