2022年算法设计与分析期末备考知识点总结 .docx

《2022年算法设计与分析期末备考知识点总结 .docx》由会员分享，可在线阅读，更多相关《2022年算法设计与分析期末备考知识点总结 .docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品_精品资料_通俗的讲,算法 是解决问题的方法, 严格的说,算法是对特定问题求解步骤的一种描述, 是指令的有限序列.算法 仍必需满意一下 五个重要特性 ：输入、输出、有穷性、确定性、可行性.程序 （ Program）是对一个算法使用某种程序设计语言的详细实现,原就上,算法可以用任何一种程序设计语言来实现.什么是算法的运算复杂性？算法分析指 的是对算法所需要的两种运算机资源时间和空间时间复杂性和空间复杂性进行估算,所需要的资源越多,该算法的复杂性就越高.表示 运算复杂性的O 你把握了？如存在两个正的常数c 和 n0,对于任意 n n0,都有 Tn c fn,就称 Tn=Ofn（或称算法在 Of

2、n中）.我们主要介绍了哪几种算法设计方法？分治法：将一个难以直接解决的大问题,分割成一些规模较小的子问题,以便各个击破,分而治之.减治法： 减治法在将原问题分解为如干个子问题后,利用了规模为n 的原问题的解与较小规模（通常是 n/2 ）的子问题的解之间的关系,这种关系通常表现为：（1） 原问题的解只存在于其中一个较小规模的子问题中.（2） 原问题的解与其中一个较小规模的解之间存在某种对应关系.由于原问题的解与较小规模的子问题的解之间存在这种关系,所以,只需求解其中一个较小规模的子问题就可以得到原问题的解.动态规划法、贪心算法、回溯算法、概率RAM 程序分治法合并排序可编辑资料 - - - 欢迎

3、下载精品_精品资料_设算法 4.3 对 n 个元素排序的时间复杂性为Tn,就该二路归并排序算法存在如下递推式：可编辑资料 - - - 欢迎下载精品_精品资料_2二路归并排序的时间代价是Onlogn.可编辑资料 - - - 欢迎下载精品_精品资料_所需空间只 要 Om+n+minm, n 的空间就够了 假设两个合并串的长度分别为m 和 n.分治法快速排序可编辑资料 - - - 欢迎下载精品_精品资料_在最好情形下在具有n 个记录的序列中, 一次划分需要对整个待划分序列扫描一遍,就所需时间为 On.时间复杂度为 Onlog2n .在最坏情形下必需经过n-1 次递归调用才能把全部记录定位,而且第i

4、趟划分需要经过n-i次关键码的比较才能找到第i 个记录的基准位置,因此,总的比较次数为：时间复杂度为On2分治法最大子段递推式：算法时间复杂度：Onlog2n分治法棋盘掩盖问题可编辑资料 - - - 欢迎下载精品_精品资料_Tk满意如下递推式：分治法循环赛日支配问题可编辑资料 - - - 欢迎下载精品_精品资料_基本语句的执行次数是：算法的其时间复杂性为O4k.次序统计问题：算法 找出 n 个元素中的第 k 个最小元素输入 ：从一个有线性序的集合中抽出的输出 ： S 中的第 k 个最小元素n 个元素的序列S 及一个整数 k, 1k n.算法 2算法 2 的期望时间是 On.最坏情形 On2减治

5、插入排序（手工题）可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_堆的概念：n 个元素的序列 K1,K2,.Kn,当且仅当满意可编辑资料 - - - 欢迎下载精品_精品资料_动态规划求解 TSP问题注：用动态规划解决 TSP问题,算法的时间复杂性为 On22n.和蛮力法相比, 动态规划法求解 TSP问题,把原先的时间复杂性是 On.的排列问题,转化为组合问题,从而降低了算法的时间复杂性,但它仍需要指数时间. 但遗可编辑资料 - - - 欢迎下载精品_精品资料_憾的是这一动态规划算法需要 On2n的空间.当 n 较大时,空间难以满意.多段图的最短路

6、径算法：1For i=1; i=0; i-2.1 对顶点 i 的每一个邻接点 j,依据costi=mincij+costj ij n 且顶点 j 是顶点 i 的邻接点 运算 costi;2.2 依据 pathi= 使 cij+costj最小的 j运算 pathi; 3输出最短路径长度 cost0;4. 输出最短路径经过的顶点：4.1 i=04.2 循环直到 pathi=n-14.2.1 输出 pathi;4.2.2 i=pathi;最优二叉查找树算法：最优二叉查找树 是以这 n 个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树,即 最小,其中 pi 是记录 ri 的查找概率, ci 是

7、在二叉查找树中查找 ri 的比较次数.可编辑资料 - - - 欢迎下载精品_精品资料_回溯法 解空间树的动态搜寻过程注：搜寻过程中,采纳两种策略防止无效搜寻：1. 用约束条件剪去得不到可行解的子树.2. 用目标函数剪去得不到最优解的子树.注：树枝左侧为 1,右侧为 0,1 代表装包, 0 代表不装包,从上到下每一层代表一个物体例二: 对于 n=4 的 TSP问题,解空间树如下：代价矩阵C如下：例一: 对于 n=3 的 0/1 背包问题,三个物品的重量为 20, 15, 10,价值为20, 30, 25,背包涵量为 25,从图 8.2 所示的解空间树的根结点开头搜寻,搜寻过程如下:1. 目标函数

8、初始化为.2. 从结点 1 挑选第 1 棵子树到结点 2,表示在图中从顶点 1 动身.3. 从结点 2 挑选第 1 棵子树到达结点 3,表示在图中从顶点 1 到顶点 2,依代价矩阵可知路径长度为3.可编辑资料 - - - 欢迎下载精品_精品资料_4. 从结点 3 挑选第 1 棵子树到达结点 4,表示在图中从顶点 2 到顶点 3,依代价矩阵可知路径长度为 3+2=5.5. 从结点 4 挑选唯独的一棵子树到结点 5,表示在图中从顶点 3 到顶点 4,路径长度为 5+2=7,结点 5 是叶子结点,找到了一个可行解,路径为 12341,路径长度为 7+3=10,目标函数值 10 成为新的下界,也就是目前的最优解.6. 从结点 5 回溯到结点 4,再回溯到结点 3,挑选结点 3 的第 2 棵子树到结点 6,表示在图中从顶点 2 到顶点 4,路径长度为 3+8=11,超过目标函数值 10,因此,对以结点 6 为根的子树实行剪枝.搜寻后的结果图：回溯法图着色问题的算法用 m 种颜色为一个具有 n 个顶点的无向图着色设数组 colorn 表示顶点的着色情形,回溯法求解m 着色问题的算法如下：可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_回溯法 -n 皇后问题的算法可编辑资料 - - - 欢迎下载