大学算法分析和设计复习总结.doc

大学算法分析与设计复习总结 为了拿大学的那悲剧的学分，好好弄懂以下所有知识点吧。把老师的复习的提纲，特意汇总了所有考点，方便童鞋们复习。不喜勿喷！！！ 这本书是《算法设计与分析》 王红梅 编著 一共有以下12章，我们学了1、3、4、5、6、7、8、9 分别是“绪论、蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分治限界法 第1章 绪论 考点： 1、? 算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、? 描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1.??????自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.??????流程图???? ? 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.??????程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 伪代码 ?? 优点：表达能力强，抽象性强，容易理解 ? 3、? 了解非递归算法的时间复杂性分析。(P13) ?要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是： （1）??????决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）??????找出算法的基本语句。 （3）??????检查基本语句的执行次数是否只依赖问题规模。 （4）??????建立基本语句执行次数的求和表达式。 （5）??????用渐进符号表示这个求和表达式。 [例1.4]：求数组最小值算法 ?int ArrayMin(int a[ ], int n) ?{ ????? min=a[0]; ????? for (i=1; in; i++) ???????? if (a[i]min) min=a[i]; ????? return min; ?} 问题规模：n 基本语句： a[i]min T(n)= n-1=O(n) ? 4、? 掌握扩展递归技术和通用分治递推式的使用。（P15） 扩展递归技术：  通用分支递归式： ? 5、? 习题1-4，习题1-7 设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求给出伪代码描述，并用一组例子进行跟踪验证，写出验证过程。 （1）伪代码 1.???令最小距离min等于数组头两个元素R[0]和R[1]的差的绝对值； 2.???从i=0循环至in-1，对于每个R[i] 2.1?????分别求其与j=i+1至jn的数的差的绝对值； 2.2?????如果此值小于最小距离，则令新的最小距离为此值； 3.???输出最小距离。 （2）用实例进行跟踪验证 R[6]={10,5,11,16,30,14},n=6; Min=|10-5|=5; i=0,j=1, |R[i]-R[j]|=|10-5|=5; ?? j=2,|R[i]-R[j]|=|10-11|=1min;min=1; ?? j=3, |R[i]-R[j]|=|10-16|=6; ?? j=4, |R[i]-R[j]|=|10-30|=20; ?? j=5, |R[i]-R[j]|=|10-14|=4; i=1,j=2, |R[i]-R[j]|=|5-11|=6; ?? j=3, |R[i]-R[j]|=|5-16|=11; ?? j=4, |R[i]-R[j]|=|5-30|=15; ?? j=5, |R[i]-R[j]|=|5-14|=9; i=2,j=3, |R[i]-R[j]|=|11-16|=5; ?? j=4, |R[i]-R[j]|=|11-30|=19; ?? j=5, |R[i]-R[j]|=|11-14|=3; i=3,j=4, |R[i]-R[j]|=|16-30|=14; ?? j=5, |R[i]-R[j]|=|16-14|=2; i=4,j=5, |R[i]-R[j]|=|30-14|=16; 最后输出min=1  7、使用扩展递归技术求解下列递推关系式 （1） （2）  第3章 蛮力法 1、? 掌握蛮力法的设计思想： 蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解; 关键——依次处理所有元素。 ? 2、? 蛮力法的代表算法及其时间复杂度： 顺序查找，O(n) 串匹配（BF?O(n*m)?，KMPO(n+m)?， BMO(n*m)） 选择排序，O(n2) 冒泡排序，O(n2) 生成排列对象（排列问题），O(n!) 生成子集（组合问题），O(2n) 0/1背包 属于组合问题。 任务分配，哈密顿回路，TSP问题 属