大学算法分析与设计复习总结

1、大学算法分析与设计复习总结第1章 绪论考点：1、算法的5个重要特性。（P3）答：输入、输出、有穷性、确定性、可行性2、  描述算法的四种方法分别是什么，有什么优缺点。（P4）答：1.自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。2.流程图  优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。3.程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。4.伪代码  优点：表达能力强，抽象性强

2、，容易理解 3、了解非递归算法的时间复杂性分析。(P13) 要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。非递归算法分析的一般步骤是：（1）决定用哪个（或哪些）参数作为算法问题规模的度量。（2）找出算法的基本语句。（3）检查基本语句的执行次数是否只依赖问题规模。（4）建立基本语句执行次数的求和表达式。（5）用渐进符号表示这个求和表达式。例1.4：求数组最小值算法 int ArrayMin(int a , int n)       min=

3、a0;      for (i=1; i<n; i+)         if (ai<min) min=ai;      return min; 问题规模：n基本语句： ai<minT(n)= n-1=O(n) 4、掌握扩展递归技术和通用分治递推式的使用。（P15）扩展递归技术：通用分支递归式： 使用扩展递归技术求解下列递推关系式（1）（2）第2章  分治法了

4、解分治法的设计思想设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。步骤：（1）划分（2）求解子问题（3）合并 分治法的代表算法及时间复杂度：归并排序，快速排序，最大子段和，最近对问题，凸包问题，这五种问题的分治算法的时间复杂度为O(nlog2n)棋盘覆盖，循环赛日程安排为O(4k) 掌握归并排序和快速排序算法的算法伪代码。（P78-83）归并排序：算

5、法中数组r中存储原始数据，r1在中间过程中存储排序后的数据，s指需排序数组的起始下标，t指需排序数组的结束下标。最终排序后的数据依然存储在r数组中。快速排序：掌握最大子段和问题的算法伪代码。（P83-85）对于待排序列（5, 3, 1, 9, 8, 2, 4, 7）,画出快速排序的递归运行轨迹。按升序排列初始序列：5,3,1,9,8,2,4,7第一次划分：4,3,1,2,5,8,9,7第二次划分：2,3,1,4,5,8,9,7第三次划分：1,2,3,4,5,8,9,7第四次划分：1,2,3,4,5,7,8,9排序完成，红色字体为每次划分的轴值 在有序序列9（r1,r2, rn）中，存

6、在序号i ( 1<=i<=n),使得ri = i, 请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n).参考代码：#include<iostream.h>int findr(ints,int begin,int end) if(begin=end) if(sbegin=begin) return begin; else return 0; else int m=(begin+end)/2; if(sm>m) return findr(s,begin,m-1); else if (sm=m)return m; else return f

7、indr(s,m+1,end); void main() int s=0,1,1,2,4,6,8; cout<<findr(s,1,6)<<endl; 掌握选择问题的算法的伪代码（P33）  第3章 动态规划法了解动态规划法的设计思想设计思想：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。步骤：将原始问题分解为相互重叠的子问题，确定动态规划函数；求解子问题，填表；根据表，自底向上计算出原问题的解。 掌

8、握可以用动态规划法解决的问题及时间复杂度：TSP，多段图的最短路径问题，0/1背包，最长公共子序列问题，最优二叉查找树，近似串匹配问题；多段图的最短路径问题： O(n+m)0/1背包问题： O(n×C) 矩阵连乘：掌握0/1背包问题的动态规划算法及具体实现（P75） 例题：用动态规划法求如下0/1背包问题的最优解：有5个物品，其重量分别为（3，2，1，4，5），物品的价值分别为（25，20，15，40， 50），背包容量为6。写出求解过程。0/1背包问题的动态规划函数为：V(i,j)表示把前i个物品放入容量为j的背包中的最大价值和。填表过程：放入背包中的物品的求解

9、过程：则65表示把5个物品放入容量为6的背包中的最大价值和。i=5,j=6;  v56>v46,x5=1, j=6-w5=1i=4,j=1; v41=v31, x4=0i=3,j=1; v31>v21, x3=1, j=1-w3=0i=2,j=0; v21=v10, x2=0i=1,j=0; v10=v00, x1=0结果是把第3个和第5个放入了背包掌握最长公共子序列问题的动态规划法算法及具体实现（P58） 求X=“xzyzzyx”和Y=“zxyyzxz”序列的最长公共子序列的动态规划函数为：Lij表示X中前i个元素和Y中

10、前j个元素构成的序列的最长公共子序列的长度。为了确定具体的最长公共子序列，需要同时计算Sij的值，Sij表示在计算Lij的过程中的搜索状态。 子序列为斜箭头所标示的行或列：X2,X3,X6 ,X7或Y1, Y3, Y4 , Y6最长公共子序列的长度为4即为：zyyx流水作业调度：最优二叉搜索树： 第3章 贪心法了解贪心法的设计思想 贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。贪心法的关键在于决定贪心策略。 掌握可以用贪心法解决的问题：TSP问题中的两种解决方法：最近

11、领点策略，最短链接策略最小生成树问题的两种算法：最近顶点策略（Prim算法），最短边策略（Kruskal算法）背包问题，活动安排问题，多机调度问题，哈夫曼编码。 掌握最小生成树的两种贪心算法：prim算法和kruskal算法（P100-102），给出具体的例子，能够用两种方法画出树的生成过程。 掌握背包问题的贪心算法问题：求如下背包问题的最优解：有7个物品，价值P=(10,5,15,7,6,18,3),重量w=(2,3,5,7,1,4,1),背包容量W=15.解决方法：先对物品的单位重量价值按照降序排列物品重量物品价值物品价值/物品重量16621054184.5515313

12、3351.67771依次把物品放入容量为15的背包，直到背包被装满1+2+4+5+1=13，前5个物品装入背包，还剩下容量为2，第6个物品只能装入2/3所以总价值为：6+10+18+15+3+5*2/3=55.3333 给出字符集和对应的频率，能够画出对应的哈夫曼树，并对给定的字符串进行哈夫曼编码。（P92）活动安排：最优装载：第8章 回溯法了解回溯法的设计思想设计思想：从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结

13、点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。步骤：确定解向量和分量的取值范围，构造解空间树；确定剪枝函数；对解空间树按深度优先搜索，搜索过程中剪枝；从所有的可能解中确定最优解。 了解可以用回溯法解决的问题：属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：图着色问题，哈密顿回路问题，八皇后问题（4皇后问题），批处理作业调度问题。 掌握m颜色图着色判定问题的回溯法算法，并能画出解空间树的搜索过程（P168-170），习题8-4对图8.14使用回溯法求解图问题

14、，画出生成的搜索空间。解：图着色问题求解的是满足图着色要求的最小颜色数。对图8.14应该从1、2、3、4种颜色依次尝试用回溯法判定是否满足M着色的要求。经搜索，1种和2种颜色均不能满足图着色的要求，3种颜色可以满足图着色要求，搜索过程如下，所以图8.14的着色的最少颜色数应该为3搜索空间为： 掌握n皇后问题的回溯法算法，并能画出解空间树的搜索过程（P173-174）,自己看书掌握0/1背包问题的回溯算法，并能画出解空间树的搜索过程（P163-164），习题8-5自己看书第9章 分治限界法了解分支限界法的设计思想设计思想：1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down, up ，并确定限界函数；2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。