算法设计与分析复习

《算法设计与分析复习》由会员分享，可在线阅读，更多相关《算法设计与分析复习（14页珍藏版）》请在金锄头文库上搜索。

1、算法设计与分析 复习算法与程序算法：解决问题的方法或过程，是满足下述性质的指令序列。输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。描述算法与算法设计算法分析的基本原则算法分析的基本原则时间复

2、杂度(time complexity)T(n)时间复杂度指程序执行时所用的时间。在使用解析方法时程序p的时间复杂度表示为输入量的函数T。机器独立的分析方法-解析的方法.在解析地分析时间复杂度时,使用以下两种时间单位并计算：操作计数(operation count):算法的基本操作(程序)步计数(step count):分析全部程序要点:基本操作或程序步的执行时间必须是常数。最好，最坏和平均情形时间复杂度当长度相同的不同输入有不同的计算时间时，时间复杂度分析分别考虑三种情形：即最好，最坏和平均.当应用对计算时间有严格要求时，应做最坏情形分析-upper bound.最好情形分析给出一个算法的计算

3、时间的下界，用来否定一个算法.渐近分析,符号(,)计算机科学使用最多的符号-讨论算法时使用的共同语言.渐近分析-随n的增加T(n)的增长率渐近分析(续)大f(n)=(g(n) iff 存在常数 c和n 0使得对所有nn 0,有f(n)cg(n )成立. 渐近分析(续)称g(n)为f(n) 的渐近下界例如,f(n)=0.001n2-10n-1000=(n2)因为:limf(n)/n 2=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, 0 amiddle) left = midd

4、le + 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

5、= f2 = 1;for(int i = 3; i n) output(x);elsefor (int i=f(n,t);in) output(x);elsefor (int i=0;in) output(x);elsefor (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个皇后不放在同一行或同一列或同一斜线

6、上。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个数字，每个方格填一个整

7、数，使得所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。练习：走台阶问题【题目叙述】你眼前一共有n级台阶（n 为正整数） ，现在你要走完这n级台阶，已知你只能一步走一级或一步走两级，请你算算一共有多少种走法，并把这些走法都给出。 【输入输出样例】输入：3 输出：1 1 1 1 2 2 1 第六章 分支限界法6.1 分支限界法的基本思想1. 分支限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以

8、深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 6.1 分支限界法的基本思想2. 分支限界法基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 6.1 分支限界法的基本思想3. 常见的两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。6.2 单源最短路径问题1. 问题描述下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s 到目标顶点 t之间的最短路径。 6.2 单源最短路径问题下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。