大学算法与设计复习总结讲解.docx

大学算法分析与设计复习总结 第1章 绪论 考点： 1、算法的5个重要特性。（P3） 答：输入、输出、有穷性、确定性、可行性 2、? 描述算法的四种方法分别是什么，有什么优缺点。（P4） 答： 1.自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图? 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码 ?优点：表达能力强，抽象性强，容易理解 ? 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） 扩展递归技术： INCLUDEPICTURE \d /20130606171628187 \* MERGEFORMATINET  INCLUDEPICTURE \d /20130606171655812 \* MERGEFORMATINET  INCLUDEPICTURE \d /20130606171818421 \* MERGEFORMATINET  通用分支递归式： ?INCLUDEPICTURE \d /20130606171822859 \* MERGEFORMATINET  INCLUDEPICTURE \d /20130606171826968 \* MERGEFORMATINET  使用扩展递归技术求解下列递推关系式 （1） INCLUDEPICTURE \d /20130606171831250 \* MERGEFORMATINET  （2） INCLUDEPICTURE \d /20130606171836093 \* MERGEFORMATINET  第2章 ?分治法 了解分治法的设计思想 设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 步骤：（1）划分（2）求解子问题（3）合并 ? 分治法的代表算法及时间复杂度： 归并排序，快速排序，最大子段和，最近对问题，凸包问题，这五种问题的分治算法的时间复杂度为O(nlog2n) 棋盘覆盖，循环赛日程安排为O(4k) ? 掌握归并排序和快速排序算法的算法伪代码。（P78-83） 归并排序： INCLUDEPICTURE \d /20130608111247156 \* MERGEFORMATINET  算法中数组r中存储原始数据，r1在中间过程中存储排序后的数据，s指需排序数组的起始下标，t指需排序数组的结束下标。最终排序后的数据依然存储在r数组中。 INCLUDEPICTURE \d /20130608111303953 \* MERGEFORMATINET  快速排序： INCLUDEPICTURE \d /20130608111441609 \* MERGEFORMATINET  INCLUDEPICTURE \d /20130608111452703 \* MERGEFORMATINET  掌握最大子段和问题的算法伪代码。（P83-85） INCLUDEPICTURE \d /20130608111616890 \* MERGEFORMATINET  INCLUDEPICTURE \d /20130608111622593 \* MERGEFORMATINET  对于待排序列（5, 3, 1, 9, 8, 2, 4, 7）,画出快速排序的递归