算法分析与设计复习大纲

算法分析与设计复习大纲

第1章 绪论 考点：

1、 算法的5个重要特性。

答：输入、输出、有穷性、确定性、可行性

2、 掌握扩展递归技术和通用分治递推式的使用。 扩展递归技术：

通用分支递归式：

5、使用扩展递归技术求解下列递推关系式 （1）

（2）

第3章 蛮力法

1、 掌握蛮力法的设计思想：

蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;

关键——依次处理所有元素。

2、 蛮力法的代表算法及其时间复杂度： 顺序查找，O(n)

串匹配（BF O(n*m) ，KMPO(n+m) 选择排序，O(n) 冒泡排序，O(n)

生成排列对象（排列问题），O(n!) 生成子集（组合问题），O(2) 0/1背包 属于组合问题。

任务分配，哈密顿回路，TSP问题 属于排列问题。

n

22

3、 掌握BF和KMP算法的原理，能够画出比较过程。要求给出一串字符串，能够求出对应的next数组，并能使用KMP算法进行比较匹配。

4、 掌握选择排序和冒泡排序算法描述和时间复杂性，要求能够写出伪代码。 选择排序

算法描述：选择排序开始的时候，扫描整个序列，找到整个序列的最小记录和序列中的第一记录交换，从而将最小记录放到它在有序区的最终位置上，然后再从第二个记录开始扫描序列，找到n-1个序列中的最小记录，再和第二个记录交换位置。一般地，第i趟排序从第i个记录开始扫描序列，在n-i+1个记录中找到关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。 时间复杂性：O(n) 伪代码：

2

冒泡排序

算法描述：冒泡排序开始的时候扫描整个序列，在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就能被“沉到”了序列的最后一个位置，第二趟扫描将第二大记录“沉到”了倒数第二个位置，重复上述操作，直到n-1趟扫描后，整个序列就排好序了。 冒泡排序，O(n)

2

5、 算法设计题：

假设在文本“ababcabccabccacbab”中查找模式 “abccac”,求分别采用BF算法和KMP算法进行串匹配过程中的字符比较次数。

由此可知，用BF算法一共要进行3+1+4+1+1+6+1+1+1+6=25次比较方能匹配出

KMP算法：next[]={,0,1,1,1,1,2};

由此可知，用KMP算法一共要进行3+4+6+5=18次比较方能匹配出

第4章 分治法

了解分治法的设计思想

设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 步骤：（1）划分（2）求解子问题（3）合并

分治法的代表算法及时间复杂度：

归并排序，快速排序，最大子段和，最近对问题，这五种问题的分治算法的时间复杂度为O(nlog2n) 棋盘覆盖为O(4)

掌握归并排序和快速排序算法的算法伪代码。 归并排序：

k

算法中数组r中存储原始数据，r1在中间过程中存储排序后的数据，s指需排序数组的起始下标，t指需排序数组的结束下标。最终排序后的数据依然存储在r数组中。

快速排序：

对于待排序列（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

排序完成，红色字体为每次划分的轴值

第5章 减治法

了解减治法的设计思想

设计思想：原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。

掌握使用减治法的代表问题及时间复杂度：

折半查找，二叉树查找，堆排序，选择问题，淘汰赛冠军问题，假币问题；

以上问题的时间复杂度，如果减治是每次减小为原来规模的1/2，则时间复杂度一般为O(log2n)

掌握折半查找的算法伪代码描述及具体例子的查找过程，会根据折半查找的过程创建判定树。

会根据已知数据序列创建一个二叉查找树。（P100）

掌握堆排序算法中的两种调整堆和新建堆的方法：筛选法 堆调整问题：将一个无序序列调整为堆 （1）筛选法调整堆

本文来源：https://www.bwwdw.com/article/u93v.html