算法设计与分析复习.docx

算法设计与分析 复习算法与程序算法：解决问题的方法或过程，是满足下述性质的指令序列。输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。描述算法与算法设计算法分析的基本原则算法分析的基本原则时间复杂度(time complexity)T(n)时间复杂度指程序执行时所用的时间。在使用解析方法时程序p的时间复杂度表示为输入量的函数T。机器独立的分析方法-解析的方法.在解析地分析时间复杂度时,使用以下两种时间单位并计算：操作计数(operation count):算法的基本操作(程序)步计数(step count):分析全部程序要点:基本操作或程序步的执行时间必须是常数。最好，最坏和平均情形时间复杂度当长度相同的不同输入有不同的计算时间时，时间复杂度分析分别考虑三种情形：即最好，最坏和平均.当应用对计算时间有严格要求时，应做最坏情形分析-upper bound.最好情形分析给出一个算法的计算时间的下界，用来否定一个算法. 渐近分析,符号(,)计算机科学使用最多的符号-讨论算法时使用的共同语言.渐近分析-随n的增加T(n)的增长率渐近分析(续)大 f(n)=(g(n) iff 存在常数c和n0使得对所有nn0,有f(n)cg(n)成立. 渐近分析(续)称g(n)为f(n)的渐近下界例如, f(n)=0.001n2-10n-1000=(n2) 因为:limf(n)/n2=0.001 渐近分析(续)符号如果f(n)=O(g(n)同时 f(n)=(g(n)则f(n)=(g(n),并称f(n)与g(n)同阶.Lim f(n)/g(n)=c, 0c唴则 f(n)=(g(n)g(n)取上述初等函数渐近分析(续)当f(n)为算法的时间复杂度函数时，称g(n)为该算法的复杂度的阶。第2章 递归与分治策略算法总体思想将要求解的较大规模的问题分割成k个更小规模的子问题。2.1 递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。2.1 递归的概念例1 阶乘函数阶乘函数可递归地定义为：2.1 递归的概念例2 Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：2.1 递归的概念例4 排列问题设计一个递归算法生成n个元素r1,r2,rn的全排列非递归算法：字典序法例字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。2.1 递归的概念例5 整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。递归小结解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2.用递推来实现递归函数。3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。分治法的基本步骤divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。二分搜索技术给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。分析： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。 分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。据此容易设计出二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 = a1 = . = an-1 中搜索 x / 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。棋盘覆盖合并排序第3章 动态规划算法总体思想例：Fibonacci数列求 Fibonacci数列的第n项int f (int n) if(n=0 | n=1)return n; return f(n-1)+f(n-2);如何去除冗余动态规划int fn+1;f1 = f2 = 1;for(int i = 3; i = n; i+) fi = fi-1 + fi-2;cout fn n) output(x); else for (int i=f(n,t);in) output(x); else for (int i=0;in) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); n后问题在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。0-1背包问题 解空间：子集树 可行性约束函数： 上界函数：private static double bound(int i) / 计算上界 double cleft = c - cw; / 剩余容量 double bound = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; bound += pi; i+; / 装满背包 if (i = n) bound += pi / wi * cleft; return bound; 【问题】 填字游戏问题描述：在33个方格的方阵中要填入数字1到N（N10）内的某9个数字，每个方格填一个整数，使得所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。练习：走台阶问题【题目叙述】你眼前一共有n级台阶（n为正整数），现在你要走完这n级台阶，已知你只能一步走一级或一步走两级，请你算算一共有多少种走法，并把这些走法都给出。【输入输出样例】输入：3输出：111 12 21第六章 分支限界法6.1分支限界法的基本思想1. 分支限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 6.1分支限界法的基本思想2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 6.1分支限界法的基本思想3. 常见的两种分支限界法（1）队列式(FIFO)分支限界法 按照队列先