2022年算法复习整理 .pdf

20100230210 贡献第 1 页 共 8 页算法设计与分析复习要点2.算法的概念：答：算法是求解一类问题的任意一种特殊的方法。一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。注：算法三要素：1、操作 2、控制结构3、数据结构3.算法有 5大特性：答： 输入、输出、确定性、能行性、有穷性。注： 输入：一个算法有个或多个输入；输出：一个算法将产生一个或多个输出。确定性：一个算法中每一步运算的含义必须是确切的、无二义性的；可行性：一个算法中要执行的运算都是相当基本的操作，能在有限的时间内完成；有穷性：一个算法必须在执行了有穷步运算之后终止；4.算法按计算时间可分为两类：答:多项式时间算法的渐进时间复杂度: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、 答：程序所以来的算法。问题规模和输入数据。计算机系统系能。注：算法运行的时间代价的度量不应依赖于算法运行的软件平台，算法运行的软件包括操作系统和采用的编程语言及其编译系统。时间代价用执行基本操作（即关键操作）的次数来度量，这是进行算法分析的基础。7.关键操作的概念答：指算法运行中起主要作用且花费最多时间的操作。1. 简述分治法是怎样的一种算法设计策略：答： 将一个问题 分解 为若干个规模较小的子问题,且这些子问题互相独立且与原问题类型相同 , 递归 地处理这些子问题，直到这些子问题的规模小到可以直接求解，然后将各个子问题的解 合并 得到原问题的解。注：一个问题可以用分治法求解的三要素：问题能够按某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；问题足够小时可以直接求解；能够将子问题的解组合成原问题的解。2. 迭代法 也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。利用迭代算法解决问题，需要做好以下三个方面的工作：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 20100230210 贡献第 2 页 共 8 页一、确定迭代模型。 在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式， 指如何从变量的前一个值推出其下一个值的公式（或关系） 。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。 不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来； 另一种是所需的迭代次数无法确定。对于前一种情况， 可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。8.利用分治算法求解：二分搜索， Streem矩阵乘法， 棋盘覆盖， 合并排序， 快速排序， 线性时间选择，9.1 大整数相乘9.2 循环体育比赛日程表制订设有 n=2k个运动员要进行兵乓球循环赛。现在要设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1 个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1 天。按分治策略，将所有的选手分为两半，n 个选手的比赛日程表就可以通过为n/2 个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2 个选手时， 比赛日程表的制定就变得很简单。这时只要让这2 个选手进行比赛就可以了。9.3 距离最近的两个点问题10. 贪心法的基本思想答：把求解的问题分成若干个子问题。对每一子问题求解，得到子问题的局部最优解。把子问题的解局部最优解合成原来解问题的一个解。注：它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定标准准下看去最优的决策；决策一旦作出， 就不可再更改。制定决策的依据称为贪心准则 。贪婪法是一种不追求最优解， 只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。11.贪心法的两个特性答： 贪心选择性质 和 最优子结构性质12.利用贪心法求解：活动安排，最优装载，哈夫曼编码，最小生成树，多调度问题，12.1 最小代价生成树12.2 单源最短路径12.3 背包问题13.动态规划法的基本思想答：将待求解的问题分解成若干个相互联系的子问题，先求解子问题， 然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。20.设计一个动态规划算法的4 个基本步骤答： 1.找出最优解的性质，由此构造问题求解的最优子结构。2.根据子问题重叠特性给名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 20100230210 贡献第 3 页 共 8 页出求最优解的递归描述。3.以自底向上 的方式计算出各子问题的最优值，并保存每个子问题首次计算时的值以备后续查用；4.从最后一步的最优值回溯，即可得原问题的最优解。14.利用动态规划法求解：最长公共子序列，凸多边形最优三角分割，多边形游戏，图像压缩，电路布线，流水作业调度， 0-1背包问题，足有二叉搜索树14.1 多段图问题14.2 矩阵连乘问题15.回溯法的基本思想答：针对所给问题， 定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。16.状态空间树的概念答：描述问题解空间的树型结构。树中的每个结点称为一个问题状态 。从根结点到树中某个状态的路径代表一个作为候选解的元组，它称为 解状态 。所有的叶结点都是解状态。如果从根结点到某个解状态的路径代表一个作为可行解的元组，则称该解状态为答案状态 。回溯法解旅行售货员问题时的解空间树是：子集树17.利用回溯法求解：装载问题，批处理作业调度，符号三角形问题，最大团问题，旅行售货员问题，圆排列问题，连续邮资问题，17.1 n 皇后问题17.2 0/1 背包问题17.3 图的着色18.分枝限界法的基本思想答：分支限界法常以广度优先或以最小耗费（最大效益） 优先的方式搜索问题的解空间树。在分支限界法中， 每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后， 从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。19.FIFO 分枝限界法、 LIFO 分枝限界法、 LC 分枝限界法答：按照队列先进先出（FIFO ）原则选取下一个节点为扩展节点。按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 20100230210 贡献第 4 页 共 8 页 程序中所有语句的执行次数为Tn=2n3+3n2+2n+1 它的渐进时间复杂度为O(n3) 记号在算法复杂性的表示法中表示渐进确界或紧致界1、按照单位效益从大到小依次排列这7 个物品为： FBGDECA 。将它们的序号分别记为17。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序 1 分】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 20100230210 贡献第 5 页 共 8 页在 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，使得对任意的自然数nn2，有：G(n)c2g(n) 令 c3=maxc1,c2,n3=maxn1,n2,则对所有的nn3，有：F(n) c1f(n) c3f(n) G(n)c2g(n)c3g(n) 故有： O(f)+O(g)=F(n)+G(n)c3f(n)+c3g(n)=c3(f(n)+g(n) 因此有： O(f)+O(g)=O(f+g) (2) 求下列函数的渐近表达式3n2+10n; 21+1/n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 20100230210 贡献第 6 页 共 8 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 20100230210 贡献第 7 页 共 8 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 20100230210 贡献第 8 页 共 8 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -