递归算法的优缺点

1、精选文档递归算法的优缺点：优点：结构清楚，可读性强，而且简洁用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大便利。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。边界条件与递归方程是递归函数的二个要素应用分治法的两个前提是问题的可分性和解的可归并性以比较为基础的排序算法的最坏倩况时间简单性下界为0(nlog2n)。回溯法以深度优先的方式搜寻解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜寻解空间树T。舍伍德算法设计的基本思想:设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n

2、的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这明显不能排解存在xXn使得 的可能性。期望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有拉斯维加斯( Las Vegas )算法的基本思想:设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应当对全部输入x均有p(x)0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有：解此方程可得： 蒙特卡罗(Monte Carlo)算法的基本思想:设p是一个实数，且1/2p1。假如一个蒙

3、特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。假如对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是全都的。线性规划基本定理：假如线性规划问题有最优解，则必有一基本可行最优解。单纯形算法的特点是：（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；（2）一般经过不大于m或n次迭代就可求得最优解。单纯形算法的基本思想就是从一个基本可行解动身，进行一系列的基本可行解的变换。每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。图

4、灵机由以下几部分组成：一条无限长的带（有无穷个格子）、一个读写头、一个有限状态把握器以及一个程序。NPC形式化定义：定义1：语言L是NP完全的当且仅当（1） L【NP；（2）对于全部L【NP有L pL。 假如有一个语言L满足上述性质(2),但不肯定满足性质（1），则称该语言是NP难的。全部NP完全语言构成的语言类称为NP完全语言类，就是NPC。定理1 设L是NP完全的，则（1）LP当且仅当PNP；（2）若 L p L1，且 L1 NP，则L1是NP完全的。团问题: 任给图G和整数k试判定图G中是否存在具有k个顶点的团？ 1)团问题NP。明显，验证G的一个子图是否成团只需多项式时间即可。 2)S

5、AT团问题。 任给表达式f构造一个相应的图G如下：图G的每个顶点对应于f中的每个文字(多次消灭的重复计算)。若G中两个顶点其原对应的文字不相互补且不消灭于同一于句中，则将其连线。 设f有n个子句，则f可满足当且仅当f对应的图G中有n个顶点的团。 这是由于：(a) 若f可满足，即有某种赋值使得f取值为真，它等价于使得每个ci中都至少有一个文字为真，这n个文字(每个ci(1in)中一个)对应的图G中的n个顶点就构成一个团。(b)若图G中有一n个顶点的团，则取给出访得这n个顶点对应的文字都为真的赋值，则f的取值为真(这由图G的定义易证)。显见，上述构造图G的方法是多项式界的，因此SAT 团问题。由(

6、a)、(b)有，团问题NPC。证毕。单源最短路径问题:void shortestpaths(v) MinHeap H1000; /定义最小堆MinHeapNode E;E.i=v;E.length=0;Distv=0;/搜寻问题界空间while(true) for(j=1;j=n;j+)if(cE.ijinf)& (E.length+cE.ijdistj) distj=E.length+cE.ij; prevj=E.i; /加入活结点优先队列 MinHeapNode N;N.i=j; N.length=distj; H.Insert(N); /取下一个扩展结点 try H.DeleteMin(

7、E); /优先队列为空 catch (OutOfBounds) break;(1)数值随机化算法: 求解数值问题,得到近似解(2)Monte Carlo算法: 问题精确性,但却无法确定解正确性(3)Las Vegas算法:获得正确解,但存在找不到解的可能性(4)Sherwood算法:保证能获得正确解旅行售货员问题:(优先队列式分支限界法) Type Travding (int v) MinHeapNode H(1000)； Type MinoutN+1； /计算 Minouti=顶点 i的最小出边费用 Type Minsurn=0；/最小出边费用和for（i=1;in；i+） Min=NoEd

8、ge； for（ j=1；jn；j+） if（aij!=NoEdge(aijMin | Min=NoEdge) Min=aij； if（Min=NoEdge） return(NoEdge)； /无回路 MinOuti= Min； MinSum+=Min； /初始化 MinHeapNode E； for（i= 0；i n；i+） E.xi= i+ 1； E.s=0； E.cc=0； E.rcost=MinSum； Bestc=NoEdge； while（E.sn-1) /非叶结点if（E.sn-1） /当前扩展结点是叶结点的父结点 if（aE.xn-2E.xn-1!=NoEdge aE.xn-2

9、1!=NoEdge&（E.cc+aE.xn-2E.xn-1+aE.xn-11 n) for (int j = 1; j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j f1)?f2i-1:f1)+Mxj2; f+=f2i; if (f bestf) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj); f1- =Mxj1; f- =f2i; 所以在最坏的状况下，整个算法的计算时间简单性为O(n!)回溯算法解0-1背包问题(解空间：子集树):templateTypep Knap:Bound(int

10、i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i n ) bestp=cp; return; if(cw+wibestp ) backtrack(i+1); /xi=0由于上界函数Bound()需要O(n)的时间，在最坏的状况下有O(2n)个右儿子结点需要计算上界函数，所以0-1背包问题的回溯算法Backtrack()所需要的时间是O(n2n)。回溯算法解图的m着色问题:v

11、oid Color:Backtrack(int t) if (tn) sum+; for (int i=1; i=n; i+) cout xi ; cout endl; else for (int i=1;i=m;i+) xt=i; if (Ok(t) Backtrack(t+1); bool Color:Ok(int k)/ 检查颜色可用性 for (int j=1;j n) / 到达叶结点 for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 检查顶点 i 与当前团的连接 int OK = 1; for (int j =

12、 1; j bestn) / 进入右子树 xi = 0; Backtrack(i+1);解最大团问题的回溯算法Backtrack所需的计算时间为O(n2n)。 回溯法的基本思想是：不断用修改过的判定函数Pi只(x1,x2,xi)(亦称为限界函数)去测试正在构造中的n元组的部分向量(x1,x2,xn)看其是否可能导致最优解。假如判定(x1，x2，xn)不行能导致最优解，那么就不再测试可能要测试的mi+1mi+2.mn个向量。解符号三角形问题的回溯算法Backtrack所需的计算时间为O(n2n)。 贪心法解最优装载问题：templatevoid Loading(int x, Type w, Ty

13、pe c, int n) int *t = new int n+1; Sort(w, t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n & wti = c; i+) xti = 1; c -= wti;算法所需的计算时间为 O(nlogn)算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入 (2)输出 (3)确定性 (4)有限性：问题的计算时间下界为W(f(n)，则计算时间简单性为O(f(n)的算法是最优算法。1. 什么是动态规划法：将问题分解成多级或很多子问题，然后挨次求解子问题，

14、前一个子问题的解为后一个子问题的求解供应有用的信息。2. 什么是贪心法：从问题某一初始或推想值动身，一步步的攀登给定目标，尽可能快的去靠近更好的解，当达到某一步不能连续时终止。3. 什么是分支定界法：对有约束条件的最优化问题全部可行解定向、适当地进行搜寻。将可行解空间不断地划分为越来越小的子集（分支），并为每一个子集的解计算一个上界和下界（定界）。5、什么是NP类问题：NP=L|L是一个能在多项式时间内被一台NDTM图灵机所接受的语言，其中NDTM是非确定性图灵机。或者可说：NP是全部可在多项式时间内用不确定的算法求解的判定问题的集合。对于NP类，相当于要求验证模块在多项式时间内完成对应NDT

15、M，有非确定性算法。1. 算法的分类：1）(数值算法 ) 2） 非数值算法2. 算法的描述：1）自然语言描述 2）(流程图描述) 3）程序语言描述3. 算法的分析标准：1） 时空观念 2 ）(进展观念) 3） 设计观点 4） 沟通的观点设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)依据计算最优值时得到的信息，构造最优解。动态规划法求矩阵连乘问题：void MatrixChain(int *p，int n，int *m，int *s)for (int i = 1; i = n; i+) mii = 0; for (int r = 2;