《算法设计与分析复习要点学生版数据结构与算法》由会员分享，可在线阅读，更多相关《算法设计与分析复习要点学生版数据结构与算法（4页珍藏版）》请在金锄头文库上搜索。
1、T(n1)1n12n1分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题调试程序带来很大方便。递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目logn)学习好资料欢迎下载掌握找最大和最小元素的递归分治算法。理解并掌握归并分类（归并排序）算法，有xk的个数第9章分支限界法（了解）分支限界法的基本思想：(1)分支限界法常以广度优先或以最小耗学习好资料 欢迎下载算法设计与分析复习要点一、单项选择题（本大题共 15小题，每小题 2 分，共 30分）二、填空题（本大题共 15 空，每空 1 分，共 15分）三、分析题（本大题共 5 小题，每小题
2、5 分，共 25分）四、综合题（本大题共 4 小题， 1、2 题每题 6 分， 3 题 8 分， 4 题 10分，共 30分）第 2 章，导引与基本数据结构：什么是算法, 算法的 5 个特性；对一个算法作出全面分析的两个阶段。 P24O(g(n) ， (g(n) ， (g(n) 的含义。多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数所表示算法时间复杂度的排序：(1) (logn) (n) (nlogn) (n2) (n3)指数时间算法：计算时间用指数函数限界的算法常见的指数时间限界函数：(2n) (n！) (nn)什么是算法的复杂性： 是该算法所需要的计算机资源
3、的多少，它包括时间和空间资源。 复习栈和队列、树、图的基本知识，了解二元树、完全二元树，满二元树、二分检索树、了解图的邻接矩阵和邻接 表存储方法。 能写出图的深度优先序列和广度优先序列。 会求如下一些简单的函数的上界表达式： 3n2+10n =O(n2) 第 3、4 章 递归与分治算法 理解递归算法的优缺点，深刻理解递归算法的执行过程。如能写出解决 n 阶汉诺塔问题的解，并能分析写出 3 阶汉 诺塔问题的递归执行轨迹。递归算法的优点： 结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带 来很大方便。递归算法的缺点： 运行效率较低，耗费的计算时间和占用的存储空间
4、都多。为了达到此目的，根据具体程序的特点 对递归调用工作栈进行简化，尽量减少栈操作， 压缩栈存储空间以达到节省计算时间和存储空间的目的。 能求解或证明常见递归关系式，如n 阶汉诺塔问题的算法时间复杂度。T(n)T(n)1 n 12T(n 1) 1 n 12n 1分治法的基本思想：是将一个规模为 N的问题分解为 K个规模较小的子问题，这些子问题互相独立且与原问题相同。 递归地解这些子问题， 然后将各子问题的解合并得到原问题的解。掌握二分检索算法，如给一个实例，可以模拟出low ，hig ，mid 的运行轨迹。 知道并能证明二分检索算法平均时间 复杂度是 ( logn)：(1)(logn)(n)(
5、nlogn)(n2)(n3)指数时间算法：计算时间能画出用二元树表示的归并分类调用过程及合并过程。理解并能证明归并分类算法的时间复杂度。合并排序的时间互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。掌握二分检索算法，出该多段图问题的解。（要求根据cost(i)的含义，用递推的方法写出求解步骤，得到结果）理解并掌握0学习好资料 欢迎下载掌握找最大和最小元素的递归分治算法。理解并掌握归并分类（归并排序）算法，能画出用二元树表示的归并分类调用过程及合并过程。理解并能证明归并 分类算法的时间复杂度。合并排序的时间复杂度是： T(n)=O(nlogn) 。利用该递归式求
6、取合并排序算法时间复杂度的上界。理解并掌握快速分类（快速排序）算法，给定一个未排序数组，能分步写出快速分类中划分的执行过程。理解快速 分类算法的时间复杂度。快速排序的时间复杂度是： T(n)=O(nlogn)本章作业：1、写出用分治法求解循环赛日程表的完整程序。程序语言任意，但必须能上机运行。2、p99-4.22、P99-4.3根据 4.2 节开始所给出的二分检索策略，写一个二分检索的递归过程。3、P99-4.5作一个“三分”检索算法，它首先检查 n/3 处的元素是否等于某个 x 的值，然后检查 2n/3 处的元素。这样，或者 找到 x，或者把集合缩小到原来的 1/3 。分析此算法在各种情况下
7、的计算复杂度。第二章作业答案.docx第 5 章 贪心方法贪心方法: 是根据具体的问题, 选取一种量度标准, 按此标准对 n 个输入进行排序, 然后按该顺序一次输入一个量. 如果这个输入量和当前的部分最优解加在一起不能产生一个可行解, 则不把此输入量加入到这个部分解中, 这种 能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。贪心选择性质： 指所求问题的整体最优解可以通过一系列局部最优的选择。贪心算法的基本要素： 贪心选择性质和最优子结构性质。掌握背包问题的贪心解法，分别以重量、效益值，单位重量效益值为最优量度所得最优解的比较。三元归并模式的贪心解法和证明，能画出 3 元归并树单源点最
8、短路径的贪心解法，算法执行运行踪迹。如：给出一个带权图，能将下表的运行踪迹图补充完整迭代置初值12S1选取的结点 u -dist210dist3maxintdist430dist5100个子问题的解为后一个子问题的求解提供有用的信息。最优子结构性质：该问题的最优解包含着其子问题的最优解用指数函数限界的算法常见的指数时间限界函数：(2n)(n！)(nn)什么是算法的复杂性：是子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。理解回溯法的基本思想，掌如给一个实例，可以模拟出low，hig，mid的运行轨迹。知道并能证明二分检索算法平均时间复杂度是(学习好资料 欢迎下载3作
9、业：P121： 5.2 、5.12第3章作业答案.docx第 6 章 动态规划将问题分解成多级或许多子问题， 然后顺序求解子问题， 前一个子问题的解为后一个子问题的求解提供有用的信息。最优子结构性质：该问题的最优解包含着其子问题的最优解。动态规划算法的基本要素： 最优子结构性质和子问题重叠性质。理解并掌握多段图的动态规划求解过程，包括递推步骤。如，下面是一个多段图问题，为了求出源点s到终点t 的最短距离，假设用cost(i) 表示节点i 到终点t 的距 离( 节点i 是指下图中圆圈中的数字为i 的结点) 。试根据cost(i) 的含义用动态规划的方法求出该多段图问 题的解。（要求根据cost(
10、i) 的含义，用递推的方法写出求解步骤，得到结果）理解并掌握 0/1 背包问题的动态规划求解过程，会采用序偶直接解 n 值不大的 0/1 背包问题。第 8 章 回溯法回溯法： 是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发 搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含， 则跳过对 以该结点为根的子树的搜索， 逐层向其祖先结点回溯；否则，进入该子树， 继续按深度优先策略搜索。理解回溯法的基本思想，掌握状态空间树的画法及各种含义。掌握 n 皇后问题的算法及执行踪迹。 能画出 0/ 背包问题的状态空间树及子集
11、树。回溯法效率的因素：（ 1）产生 xk 的时间。（2）满足显约束的 xk 值的个数。（3）计算约束函数 constraint 的时间。（4）计算上界函数 bound 的时间。（5）满足约束函数和上界函数约束的所有 xk 的个数第 9 章 分支限界法（了解）分支限界法的基本思想：(1) 分支限界法常以广度优先或以最小耗费( 最大效益) 优先的方式 搜索问题的解空间树。constraint的时间。（4）计算上界函数bound的时间。（5）满足约束函数和上界函数约束的所/1背包问题的动态规划求解过程，会采用序偶直接解n值不大的0/1背包问题。第8章回溯法回溯法：是一个一次机会成为扩展结点。活结点一
12、旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。掌握二分检索算法，学习好资料 欢迎下载(2) 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有 儿子结点。在这些儿子结点中， 导致不可行解或导致非最优解的儿子结点被舍弃， 其余儿子结点被加入活结点表中。 (3) 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需 的解或活结点表这空时为止。最常见的分支限界法有两种： 队列式（ FIFO）分支限界法和优先队列式分支限界法。上课反复讲、反复强调的几个问题，要求懂原理，会设计（关键是思路，表达方法可以是语言、伪代码、代码）， 会进行复杂度分析。建议：答题时不要把所有的东西写一大段，适当分步骤、分要点， 如 XXX算法原理做什么，怎么做做什么，怎么做等
