算法设计与分析 复习整理

1、20100230210贡献算法设计与分析复习要点2. 算法的概念：答：算法是求解一类问题的任意一种特殊的方法。一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。注：算法三要素：1、操作2、控制结构3、数据结构3. 算法有5大特性：答：输入、输出、确定性、能行性、有穷性。 注：输入：一个算法有个或多个输入；输出：一个算法将产生一个或多个输出。确定性：一个算法中每一步运算的含义必须是确切的、无二义性的；可行性：一个算法中要执行的运算都是相当基本的操作，能在有限的时间内完成；有穷性：一个算法必须在执行了有穷步运算之后终止；4. 算法按计算时间可分为两类：答:多项式时间算法的渐进时间复杂度:

2、O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)，具有此特征的问题称为P为题。有效算法。 指数时间算法的渐进时间复杂度之间的关系为：O(2n)O(n!) O(nn)，具有此特征的问题称为NP问题。 注：可以带1或2这些数字来判断它们之间的大小关系。5. 一个好算法的4大特性：答：正确性、简明性、效率、最优性。注：正确性：算法的执行结果应当满足预先规定的功能和性能要求。 简明性：算法应思路清晰、层次分明、容易理解。利于编码和调试。效率：时间代价和空间代价应该尽可能的小。最优性：算法的执行时间已经到求解该类问题所需要时间的下界。6. 影响程序运行时间的因素：1、 答：程序所以来的

3、算法。 问题规模和输入数据。计算机系统系能。注：算法运行的时间代价的度量不应依赖于算法运行的软件平台，算法运行的软件包括操作系统和采用的编程语言及其编译系统。时间代价用执行基本操作（即关键操作）的次数来度量，这是进行算法分析的基础。7. 关键操作的概念答：指算法运行中起主要作用且花费最多时间的操作。1. 简述分治法是怎样的一种算法设计策略： 答：将一个问题分解为若干个规模较小的子问题,且这些子问题互相独立且与原问题类型相同,递归地处理这些子问题，直到这些子问题的规模小到可以直接求解，然后将各个子问题的解合并得到原问题的解。 注：一个问题可以用分治法求解的三要素：问题能够按某种方式分解成若干个规

4、模较小、相互独立且与原问题类型相同的子问题；问题足够小时可以直接求解；能够将子问题的解组合成原问题的解。2. 迭代法 也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

5、不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。8. 利用分治算法求解：二分搜索，Streem矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，9.1大整数相乘Function MULT(X，Y，n)/X和Y为2个小于n位的无符号整数，返回结果为X和Y的乘积XYif（n = 1）return(X * Y)elseA = X的左边n/2位： B = X的右边n/2位C =

6、 Y的左边n/2位： D = Y的右边n/2位ml = MULT(A, C, n/2)m2 = MULT(A-B, D-C, n/2)m3 = MULT(B, D, n/2)S = S * (m1左移2n位 + (m1 + m2 + m3)左移n位 + m3)return(S) /MULT9.2循环体育比赛日程表制订设有n=2k个运动员要进行兵乓球循环赛。现在要设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来

7、决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。下表是8个选手的日程安排表。9.3距离最近的两个点问题10.贪心法的基本思想答：把求解的问题分成若干个子问题。对每一子问题求解，得到子问题的局部最优解。把子问题的解局部最优解合成原来解问题的一个解。 注：它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定标准准下看去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪心准则。贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快

8、速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。11. 贪心法的两个特性 答：贪心选择性质和最优子结构性质12. 利用贪心法求解：活动安排，最优装载，哈夫曼编码，最小生成树，多调度问题，12.1最小代价生成树 普利姆算法12.2单源最短路径 地杰斯特拉12.3背包问题 最大收益和最优解13. 动态规划法的基本思想答：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以

9、后再次遇到时直接引用答案，不必重新求解。.设计一个动态规划算法的4个基本步骤答：1.找出最优解的性质，由此构造问题求解的最优子结构。2.根据子问题重叠特性给出求最优解的递归描述。3.以自底向上的方式计算出各子问题的最优值，并保存每个子问题首次计算时的值以备后续查用；4.从最后一步的最优值回溯，即可得原问题的最优解。14. 利用动态规划法求解：最长公共子序列，凸多边形最优三角分割，多边形游戏，图像压缩，电路布线，流水作业调度，0-1背包问题，足有二叉搜索树14.1多段图问题做题方法及步骤 按层次分析 得出最优解14.2矩阵连乘问题 mij运算次数 和sij断点保护 的求法 15. 回溯法的基本思

10、想答：针对所给问题，定义问题的解空间； 确定易于搜索的解空间结构； 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。16.状态空间树的概念答：描述问题解空间的树型结构。树中的每个结点称为一个问题状态。从根结点到树中某个状态的路径代表一个作为候选解的元组，它称为解状态。所有的叶结点都是解状态。如果从根结点到某个解状态的路径代表一个作为可行解的元组，则称该解状态为答案状态。回溯法解旅行售货员问题时的解空间树是：子集树17. 利用回溯法求解：装载问题，批处理作业调度，符号三角形问题，最大团问题，旅行售货员问题，圆排列问题，连续邮资问题，17.1 n皇后问题 四皇后问题 17.2 0/

11、1背包问题17.3 图的着色18. 分枝限界法的基本思想答：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。19. FIFO分枝限界法、LIFO分枝限界法、LC分枝限界法答：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。按照优先队列中规定的

12、优先级选取优先级最高的节点成为当前扩展节点。分支限界法解旅行售货员问题时活结点表的组织形式是：最小堆20.最优子结构：问题的最优解包含其子问题的最优解 20.用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制试题：2.矩阵乘法如下for(int=0;in;i+) for(j=0;jn;j+) Cij=0; for(k=0;kn;k+) Cij+=aik*bkj; 程序中所有语句的执行次数为Tn=2n3+3n2+2n+1 它的渐进时间复杂度为O(n3) 记号在算法复杂性的表示法中表示 渐进确界或紧致界 1、 按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为17。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】在Q1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】(1) 证明证明证明证明O(f)+O(g)=O(f+g)证明：令F(n)=O(f),则存在自然数n1、c1，使得对任意的自然数nn1，有：F(n)c1f(n)同理可令G(n)=O(g),则存在自然数n2、c2，使得对