算法知识点总结范文.doc

算法知识点总结范文 算法是指解决问题的一种方法或一个过程。 更严格的讲，算法是若干指令的有穷序列。 性质 (1)输入有零个或者多个由外部提供的量作为算法的输入。 作为算法加工对象的量值，通常体现为算法中的一组变量。 (2)输出算法产生至少一个量作为输出。 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。 (3)确定性组成算法的每条指令是清晰、无歧义的。 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行（可行性）。 并且在任何条件下，算法都只有一条执行路径。 (4)有限性算法中每条指令的执行次数是有限的，每条指令的执行时间也是有限的。 程序和算法的区别程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质 (4)有限性。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序，通过特定的算法来实现。 该子程序得到输出结果后便终止。 算法分析是对一个算法所消耗资源进行估算。 资源消耗指时间、空间的耗费。 算法分析的目的就是通过对解决同一问题的多个不同算法进行时空耗费这两方面的分析.比较求解同一问题的多个不同算法的效率。 一般情况下将最坏情况下的时间耗费的极限作为算法的时间耗费，称为时间复杂性。 可操作性最好最有实际价值的是最坏情况下的时间复杂性。 渐进复杂性当n单调增加且趋于时，T(n)也将单调增加且趋于。 对于T(n)，如果存在T(n)，当n时，(T(n)-T(n)/T(n)0，称T(n)是T(n)当N时的渐近性态，或称为算法A当N的渐近复杂性。 渐进意义下的记号O?o以下设f(N)和g(N)是定义在整数集上的正函数。 O:如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N).这时还说f(N)的阶不高于g(N)的阶。 根据符号O的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界，这个上界的阶越低，则评估就越精细，结果就越有价值。 ?如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N),则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=?(g(N).这时还说f(N)的阶不低于g(N)的阶。 根据符号?的定义，用它评估算法的复杂性，得到的只是该复杂性的一个下界，这个下界的阶越高，则评估就越精细，结果就越有价值。 定义f(N)=(g(N)，当且仅当f(N)=O(g(N)且f(N)=?(g(N)，这时我们说f(N)与g(N)同阶。 O:如果对于任意给定的0,都存在正整数N0，使得当NN0时，有f(N)/g(N) 递归的基本要素1初始值（边界条件），每个递归函数都必须有非递归定义的初始值。 2递归定义式（递归方程）。 阶乘函数可递归地定义为n!=1n=0（边界条件，给出了这个函数的初值，是非递归定义的，这是每个函数所必须的，否则递归函数就无法计算。 ）和n(n-1)!n0（是递归方程）Int factorial(int n)if(n=0)return1;return n*factorial(n-1);直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为。 分治法的基本思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同，递归的解这些子问题，然后将各子问题的解合并得到原问题的解。 它的一般的算法设计模式如下divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题divide Pinto smallersubinstances P1,P2,.,Pk；/分解问题for(i=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题return merge(y1,.,yk);/将各子问题的解合并为原问题的解其中|P|表示问题P的规模n0为一阈值，表示当问题P的规模不超过n0时，问题已容易解出，不必再继续分解。 adhoc(P)是该分治法中的基本子算法，用于直接解小规模的问题P。 当p的规模不超过n0时直接用算法adhoc(P)求解。 merge(y1,.,yk)是该分治法中的合并子算法，用于将P的子问题P1，P2，Pk合并为P的解。 二分搜索技术给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。 基本思想将n个元素分成个数大致相同的两半，取an/2与x做比较。 如果x=an/2.则找到x,算法终止。 如果xan/2,则只要在数组a的的右半部分继续搜索x具体算法如下templateint BinarySearch(Type a,const Type&x,int n)/在a0=a1=.=an-1中搜索x/找到x时返回其在数组中的位置，否则返回-1int left=0；int right=n-1；while(leftam)left=m+1;else lright=m-1;return-1;/未找到x二分搜索法算法复杂度分析每执行一次算法的while循环，待搜索数组的大小减少1/2。 因此，在最坏情况下，while循环被执行了O(logn)次。 循环体内运算需要O (1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。 而如果按顺序搜索法需用O（n)次比较。 合并排序基本思想将待排序元素分成2个子集合，分别对子集合进行排序，最终将排好序的子集合合并为有序集合。 n=1时中止。 可递归void MergeSort(Type a,int left,int right)if(left (1)n1和2T（n/2）+O（n)n1解得T（n)=O(nlogn).由于排序问题的计算时间下界为?（nlogn),故合并排序算法是一个渐近最优算法。 非递归思想相邻元素（子数组段）两两配对，用合并算法将其排序，构成2/n组长度为2的排好序的子数组段，然后再将它们排序成长度为4的排好序的子数组段，如此下去，直至整个数组排好序。 算法templatevoid MergeSort(Type a,int n)Type*b=new Typen;Int s=1;while(s 子问题的解往往不是相互独立的。 在求解的过程中，许多子问题的解被反复地使用。 为避免重复计算，动态规划算法采用填表保存子问题的解。 算法用表格保存已求解的子问题的解，无论它是否会被用到。 以后遇到该子问题时即可查表取出其解，避免了重复计算。 动态规划算法与分治法的不同适用于动态规划法求解的问题，经分解得到的子问题往往不会相互独立的。 在用分治法求解时，有些子问题被重复计算了许多次。 动态规划算法的步骤1找出最优解的性质，并刻画其结构特征。 2递归地定义最优值。 3以自底向上的方式计算最优值。 （最优值）4根据计算最优值时得到的信息，构造最优解。 （最优解）。 动态规划算法的基本要素(性质）1最优子结构性质。 问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质。 在动态规划算法中，利用问题的最优子结构性质，以自底而上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。 2子问题的重叠性质。 子问题之间并非相互独立的，而是彼此有重叠的。 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。 这种性质称为子问题的重叠性质。 备忘录方法是动态规划算法的变形，用表格保存已经计算的子问题的解备查。 备忘录算法int LookupChain(int i，int j)/自顶向下的方法，i1，jn；/m最优值数组，s最优断开位置数组。 m已赋初值为0；if(mij0)return mij;/mij初值为零；if(i=j)return0;int u=LookupChain(i，i)+LookupChain(i+1，j)+pi-1*pi*pj;sij=i;for(int k=i+1;k 2备忘录只求必须计算的子问题，而动态规划全部求解。 备忘录方法与直接递归方法相同点与不同点备忘录方法的控制结构与直接递归方法的控制结构相同，与直接递归的区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。 最长公共子序列问题具有最优子结构性质设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则 (1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。 （反证法，两个结论） (2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。 （反证法Z是xm-1和Y的公共子序列，但不是最长的） (3)若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。 其中，Xm-1=x1,x2，xm-1;Yn-1=y1,y2,yn-1;Zk-1=z1,z2.zk-1.子问题的递归结构由最优子结构性质建立子问题最优值的递归关系用cij记录序列X和Y的最长公共子序列的长度，其中，Xi=x1,x2,xi；Yj=y1,y2,yj。 当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。 故Cij=0。 其他情况下，由最优子结构性质可建立递归关系如下长度另有最长公共子序列的算法当Xm=Ym时，找出Xm-1和Ym-1的最长公共子序列，然后在结尾加上Xm(=Ym)即可得X和Y的最长公共子序列。 当XmYm时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Ym-1的一个最长公共子序列，这两个中较长者即为X和Y的最长公共子序列。 构造最长公共子序列LCSLength只是计算出最优值，并未给出最优解，然而数组b可用于快速构造两个序列的最长公共子序列bij=1时表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列加上xi所得到(斜)；bij=2时表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同（上）；bij=3时表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同（左）。 根据b的内容打印出最长公共子序列构造最长公共子序列算法void LCS(int i，int j，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，b);cout流水作业调度的Johnson法则算法复杂度分析算法的主要计算时间花在对作业集的排序。 因此，在最坏情况下算法所需的计算时间为O(nlogn)。 所需的空间为O(n)。 代码int FlowShop(int n,int a,int b,int c)class JobtypePublic;int operator=(Jobtype a)constreturn(key=a.key);int key,index;bool job;:Jobtpye*d=new Jobtypen;for(int i=0;ibi?bi:ai;di.job=ai=bi;di.index=i;sort(d,n);int j=0,k=n-1;for(int i=0;i 而m1c中的值就是该背包问题的解。 二维数组m中最先填入只能选择物品n的最优解m(n,j)若0jwn，mnj=0；若jwn，mnj=vn。 然后从物品n1到物品1逐个填入它们的最优解m(i,j)若0jwi，mij=mi+1j;若jwi，mij=maxmi+1j,mi+1jwi+vi算法的时间复杂性是O(nc)。 跳跃点的计算步骤:初始化Pn+1=(0,0)；i从n到1重复做第一步qi+1=pi+1?(wi,vi)；其中Pi+1?(wi,vi)=(a+wi,b+vi)|(a,b)Pi+1第二步pi=pi+1?qi+1；第三步删除第二步的受控点；重复1-3.实例n=5，c=10，w=2,2,6,5,4，v=6,3,5,4,6。 初始时p6=(0,0)，(w5,v5)=(4,6)。 因此，q6=p6(w5,v5)=(4,6)。 p5=p6q6=(0,0),(4,6)。 q5=p5(w4,v4)=(5,4),(9,10)。 将受控跳跃点(5,4)清除后，得到p4=del_control(p5q5)=(0,0),(4,6),(9,10)q4=p4(6，5)=(6，5)，(10，11)p4=(0,0),(4,6),(9,10)q4=p4(6，5)=(6，5)，(10，11)p3=(0，0)，(4，6)，(9，10)，(10，11)q3=p3(2，3)=(2，3)，(6，9)p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1最后的跳跃点(8,15)给出所求的最优值为m(1,c)=15。 时间复杂度计算跳跃点集所花费的时间为O(二的n次方）改进后的算法复杂性为O(minnc,2的n次方)。 贪心算法的基本要素具有2个重要性质贪心选择性质和最优子结构性质。 1贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到。 这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 2当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法与动态规划算法的差异共同点贪心算法和动态规划算法都要求问题具有最优子结构性质。 不同点满足贪心选择性质必满足最优子结构性质。 但是满足最优子结构性质却未必满足贪心选择性质。 问题能用动态规划法解的不一定能用贪心算法解；反之能用贪心法一定能用动态规划法，但是，贪心算法的效率一般高于动态规划法，因而还是应用贪心算法。 背包问题和0-1背包问题的异同这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 用贪心算法解背包问题的基本步骤计算每种物品单位重量的价值vi/wi依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。 若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去，直到背包装满为止。 算法void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for(i=1;i=n;i+)xi=0;float c=M;for(i=1;ic)break;xi=1;c-=wi;if(i=n2）时，Kruskal算法要比Prim算法差；当e=O(n2)(en)output(x);/tn时已搜索到一个叶结点,output(x)对得到的可行解x进行记录或输出处理.else for(int i=f(n,t);i0)if(f(