2022年算法设计与分析复习要点 .pdf

《2022年算法设计与分析复习要点 .pdf》由会员分享，可在线阅读，更多相关《2022年算法设计与分析复习要点 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习好资料欢迎下载11( )2 (1)11( )21nnT nT nnT n算法设计与分析复习要点一、单项选择题（本大题共15 小题，每小题2 分，共 30 分）二、填空题（本大题共15 空，每空1 分，共 15 分）三、分析题（本大题共5 小题，每小题5 分，共 25 分）四、综合题（本大题共4 小题， 1、2 题每题 6 分， 3 题 8 分， 4 题 10 分，共 30 分）第 2 章，导引与基本数据结构：什么是算法 , 算法的 5 个特性；对一个算法作出全面分析的两个阶段。P24 O(g(n) ， (g(n)，(g(n)的含义。多项式时间算法：可用多项式（函数）对其计算时间限界的算法。

2、常见的多项式限界函数所表示算法时间复杂度的排序：(1) (logn) (n) (nlogn) (n2) (n3)指数时间算法：计算时间用指数函数限界的算法常见的指数时间限界函数：(2n) (n ！) (nn) 什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。复习栈和队列、树、图的基本知识，了解二元树、完全二元树，满二元树、二分检索树、了解图的邻接矩阵和邻接表存储方法。能写出图的深度优先序列和广度优先序列。会求如下一些简单的函数的上界表达式：3n2+10n =O(n2) 第 3、 4 章 递归与分治算法理解递归算法的优缺点，深刻理解递归算法的执行过程。如能写出解决n

3、阶汉诺塔问题的解，并能分析写出3 阶汉诺塔问题的递归执行轨迹。递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。能求解或证明常见递归关系式，如n 阶汉诺塔问题的算法时间复杂度。分治法的基本思想： 是将一个规模为N的问题分解为K个规模较小的子问题， 这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。掌握二

4、分检索算法，如给一个实例，可以模拟出low， hig ，mid 的运行轨迹。知道并能证明二分检索算法平均时间复杂度是(logn) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 4 页学习好资料欢迎下载掌握找最大和最小元素的递归分治算法。理解并掌握归并分类（归并排序）算法，能画出用二元树表示的归并分类调用过程及合并过程。理解并能证明归并分类算法的时间复杂度。合并排序的时间复杂度是：T(n)=O(nlogn)。利用该递归式求取合并排序算法时间复杂度的上界。理解并掌握快速分类（快速排序）算法，给定一个未排序数组，能分步写出快速分类中划分的执

5、行过程。理解快速分类算法的时间复杂度。快速排序的时间复杂度是：T(n)=O(nlogn) 本章作业：1、写出用分治法求解循环赛日程表的完整程序。程序语言任意，但必须能上机运行。2、p99-4.2 2、P99-4.3 根据 4.2 节开始所给出的二分检索策略，写一个二分检索的递归过程。3、P99-4.5 作一个“三分”检索算法，它首先检查n/3 处的元素是否等于某个x 的值，然后检查2n/3 处的元素。这样，或者找到 x，或者把集合缩小到原来的1/3 。分析此算法在各种情况下的计算复杂度。第二章作业答案 .docx第 5 章 贪心方法贪心方法 : 是根据具体的问题, 选取一种量度标准, 按此标准

6、对n 个输入进行排序, 然后按该顺序一次输入一个量. 如果这个输入量和当前的部分最优解加在一起不能产生一个可行解, 则不把此输入量加入到这个部分解中, 这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择。贪心算法的基本要素：贪心选择性质和最优子结构性质。掌握背包问题的贪心解法，分别以重量、效益值，单位重量效益值为最优量度所得最优解的比较。三元归并模式的贪心解法和证明，能画出3 元归并树单源点最短路径的贪心解法，算法执行运行踪迹。如：给出一个带权图，能将下表的运行踪迹图补充完整迭代S 选取的结点u dist2 dist3

7、 dist4 dist5 置初值1 - 10 maxint 30 100 1 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 4 页学习好资料欢迎下载3 作业：P121： 5.2 、5.12 第3章 作业答案 .docx第 6 章 动态规划将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。最优子结构性质：该问题的最优解包含着其子问题的最优解。动态规划算法的基本要素：最优子结构性质和子问题重叠性质。理解并掌握多段图的动态规划求解过程，包括递推步骤。如，下面是一个多段图问题，为了求出源

8、点s到终点 t 的最短距离，假设用cost(i)表示节点 i 到终点 t 的距离( 节点 i 是指下图中圆圈中的数字为i 的结点 )。试 根据 cost(i)的含义用动态规划的方法求出该多段图问题的解。（要求根据cost(i)的含义，用递推的方法写出求解步骤，得到结果）理解并掌握0/1 背包问题的动态规划求解过程，会采用序偶直接解n 值不大的0/1 背包问题。第 8 章 回溯法回溯法： 是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树

9、的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。理解回溯法的基本思想，掌握状态空间树的画法及各种含义。掌握n 皇后问题的算法及执行踪迹。能画出 0/ 背包问题的状态空间树及子集树。回溯法效率的因素：（1）产生 xk 的时间。（2）满足显约束的xk 值的个数。（3）计算约束函数constraint的时间。（4）计算上界函数bound 的时间。（5）满足约束函数和上界函数约束的所有xk 的个数第 9 章 分支限界法（了解）分支限界法的基本思想：(1) 分支限界法常以广度优先或以最小耗费( 最大效益 ) 优先的方式搜索问题的解空间树。精选学习资料 - - - - - - -

10、- - 名师归纳总结 - - - - - - -第 3 页，共 4 页学习好资料欢迎下载(2) 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。 在这些儿子结点中， 导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。(3) 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。最常见的分支限界法有两种：队列式（ FIFO）分支限界法和优先队列式分支限界法。上课反复讲、反复强调的几个问题，要求懂原理，会设计（关键是思路，表达方法可以是语言、伪代码、代码），会进行复杂度分析。建议 ：答题时不要把所有的东西写一大段，适当分步骤、分要点，如XXX算法原理做什么，怎么做做什么，怎么做等精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 4 页