算法竞赛入门经典授课教案第8章高效算法设计.doc资源-CSDN文库

版权申诉

文档资料

10 浏览量 2022-05-08 12:16:12 上传评论收藏 358KB DOC 举报

资源推荐

资源详情

资源评论

第 8 章高效算法设计

【教学内容相关章节】

8.1 算法分析初步 8.2 再谈排序与搜索 8.3 递归与分治

8.4 贪心法

【教学目标】

（1）理解“基本操作”、渐近时间复杂度的概念和大 O 记号的含义；

（2）掌握“最大连续和”问题的各种算法及其时间复杂度分析；

（3）正确认识算法分析的优点和局限性，能正确使用分析结果；

（4）掌握归并排序和逆序对统计的分治算法；

（5）掌握归并排序和快速选择算法；

（6）熟练掌握二分查找算法，包括找上下界的算法；

（7）能用递归的方式思考和求解问题；

（8）熟练掌握用二分法求解非线性方程的方法；

（9）熟练掌握用二分法把优化问题转化为判定问题的方法；

（10）熟悉能用贪心法求解的各类经典的问题。

【教学要求】

理解渐近时间复杂度的概念和大 O 记号的含义；正确认识算法分析的优点和局限性，

能正确使用分析结果；掌握归并排序和快速排序算法；熟练掌握二分查找算法；熟悉能用

贪心法求解的各类经典的问题。

【教学内容提要】

本章介绍了设计高效算法的方法，首先介绍了分析算法效率的工具是渐近时间复杂度，

并给出了大 O 记号的含义；接着介绍了分治法，用它去对数组进行归并排序或快速排序，

以及查找过程中使用二分法；还介绍了贪心法求解问题。

【教学重点、难点】

教学重点：

（1）渐近时间复杂度的概念和大 O 记号的含义，并能对算法进行分析；

（2）掌握归并排序和快速排序算法；

（3）熟练掌握二分查找算法；

（4）熟悉能用贪心法求解的各类经典的问题。

教学难点：

（1）掌握归并排序和快速排序算法；

（2）熟练掌握二分查找算法；

（3）熟悉能用贪心法求解的各类经典的问题。

【课时安排】

8.1 算法分析初步 8.2 再谈排序与搜索 8.3 递归与分治

8.4 贪心法

第 231 页

第 8 章高效算法设计

下面介绍另外一种推导方法：算法包含 3 重循环，内层最坏情况下需要循环 n 次，中

层循环最坏情况下也需要 n 次，外层循环最坏情况下仍然需要 n 次，因此总运算次数不超

过 n

。这就是“上界分析。上界也有记号：T(n)=O(n

)。

提示 8-4：在算法设计中，常常不进行精确分析，而是假定各种最坏情况同时取到，

得到上界。在很多情况下，这个上界和实际情况同阶（称为“紧”的上界），但也有可能会

因为分析方法不够好，得到“松”的上界。

下面来优化这个算法。设 S

+…+A

，则 A

i+1

+…+A

-S

i-1

，它的含义

是连续子序列之和等于两个前缀和之差。这样最内层的循环就可以省略。

程序 8-2 最大连续和（2）

S[0] = 0;

for(i = 1; i <= n; i++) S[i] = S[i-1] + A[i];

for(i = 1; i <= n; i++)

for(j = i; j <= n; j++) { //更新最大值

if(S[j] - S[i-1] >= best){

best = S[j] - S[i-1];

tot++;

}

注意：上面的程序用到了递推的思想：从小到大依次计算 S[1],S[2],S[3]…,每个只需

要在前一个的基础上加上一个元素。换句话说，“计算 S”的步骤的时间复杂度为 O(n)。接

下来是一个二重循环，用类似的方法可以分析出：

同样地，用上界分析可以更快地得到结论：内层循环最坏情况下要执行 n 次，外层也是，

因此时间复杂度为 O(n

)。

8.1.3 分治法

分治法解决问题，一般分为如下 3 个步骤：

（1）划分问题：把问题的实例划分成子问题；

（2）递归问题：递归解决子问题；

（3）合并问题：合并子问题的解得到原问题的解。

在本例中，“划分”就是把序列分成元素个数尽量相等的两半；“递归求解”就是分别求出

完全位于左半或完全位于右半的最佳序列；“合并”就是求出起点位于左半、终点位于右半

的最大连续和序列，并和子问题的最优解比较。

关键在于“合并”步骤。既然起点位于左半，终点位于右半，可以人为地把这样的序列

分成两部分，然后独立求解：先寻找最佳起点，然后再寻找最佳终点。

程序 8-3 最大连续和（3）（如图 8-1 所示）

int maxsum(int* A, int x, int y) {

int i, m, v, L, R, max;

if(y - x == 1) return A[x]; //只有一个元素，直接返回

m = x + (y-x)/2; //分治第一步：划分成[x,m)和[m,y)

//分治第二步：递归求解

max = maxsum(A, x, m) > maxsum(A, m, y)? maxsum(A, x, m) ：

maxsum(A, m, y);

第 233 页

第 8 章高效算法设计

v = 0; L = A[m-1]; //分治第三步：合并（1）—从分界点开始往左的最大连续和 L

for(i = m-1; i >= x; i--) {

v += A[i];

if(v > L) L=v;

}

v = 0; R = A[m]; //分治第三步：合并（2）—从分界点开始往右的最大连续和 R

for(i = m; i < y; i++){

v += A[i];

if(v > R) R=v;

}

if(L+R > max) max = L + R; //把子问题的解与 L 和 R 比较

return max;

}

图 8-1 最大连续和的分治算法

注意：上面程序的 L 和 R 分别为从分界线往左、往右能达到的最大连续和。对于 t(n)

需要用递归的思路进行分析：设序列长度为 n 时的 tot 值为 T(n) ，则 T(n)=2T(n/

2)+n，T(1)=1。其中 2T(n/2)是两次长度为 n/2 的递归调用，而最后的 n 是合并的时间

（整个序列恰好扫描一遍）。

提示 8-5：在算法分析中，往往可以忽略“除法结果是否为整数”，而直接按照实数除

法分析。这样的近似对结果影响很小，一般不会改变渐近时间复杂度。

提示 8-6：递归方程 T(n)=2T(n/2)+n，T(1)=1 的解为 T(n)=Θ(nlogn)。

8.1.4 正确对待算法分析结果

对于“最大连续和”问题，先后介绍了时间复杂度 O(n

)、O(n

)、O(nlogn)的算法，每

个新算法较前一个算法来说，都有是重大的改进。尽管分治法看上去很巧妙，它并不是最

高效的。把 O(n2)算法稍作修改，便可以得到一个 O(n)算法：当 j 确定时，“S[j]-S[i-1]最

大”相当于“S[i-1]最小”，因此只需要扫描一次数组，维护“目前遇到过的最小 S”即可。

把渐近时间复杂度为多项式的算法称为多项式时间算法（ polymonial-time

algorithm），也称为有效算法；而 n!或者 2

这样的低效的算法称为指数时间算法

（exponential-time algorithm）。

不过需要注意的是，上界分析的结果在趋势上能反映算法的效率，但有两个不精确性：

一是公式本身的精确性；二是对程序实现细节与计算机硬件的依赖性。

8.2 再谈排序与检索

8.2.1 归并排序

第一种高效排序算法是归并排序。按照分治三步法，对归并排序算法介绍如下：

（1）划分问题：把序列分成元素个数尽量相等的两半；

（2）递归问题：把两半元素分别排序；

（3）合并问题：把两个有序表合并成一个。

前两部分很容易完成的，关键在于如何把两个有序表合并成一个。图 8-2 演示了一个

合并的过程。每次只需要把两个序列的最小元素加以比较，删除其中的较小元素并加入合

并后的新表即可。由于需要一个新表来存放结果，所以附加空间 n。

第 234 页

第 8 章高效算法设计

图 8-2 合并过程：时间是线性的，需要线性的辅助空间

归并排序的代码如下：

程序 8-4 归并排序（从小到大）

void merge_sort(int* A, int x, int y, int* T) {

if(y-x > 1){

int m = x + (y-x)/2; //划分

int p = x, q = m, i = x;

merge_sort(A, x, m, T); //递归求解

merge_sort(A, m, y, T); //递归求解

while(p < m || q < y) {

if(q >= y || (p < m && A[p] <= A[q])) //从左半数组复制到临时空间

T[i++] = A[p++];

else //从右半数组复制到临时空间

T[i++] = A[q++];

}

for(i = x; i < y; i++) A[i] = T[i]; //从辅助空间复制到 A 数组

}

代码中的两个条件是关键。首先，只要有一个序列非空，就要继续合并

（while(p<m||q<

y)）,所以正确的方式是：

（1）如果第二个序列为空（此时第一个序列一定非空），复制 A[p]。

（2）否则（第二个序列非空），当且仅当第一个序列也非空，且 A[p]≤A[q]时，才

复制 A[p]。

例 8-2 逆序对数。

给一列 a

,…,a

，求它的逆序对数，即有多少个有序对(i,j)，使得 i<j 但 a

。n

可以高达 10

。

【分析】

受到归并排序的启发，可以用“分治三步法”来做：

（1）划分问题：把序列分成元素个数尽量相等的两半；

（2）递归问题：统计 i 和 j 均在左边或者均在右边的逆序对个数；

（3）合并问题：统计 i 在左边，但 j 在右边的逆序对个数。

解决本问题的关键在于合并：如何求出 i 在左边，而 j 在右边的逆对序对数目呢：按照

j 的不同把这些“跨越两边”的逆序对进行分类：只在对于右边的每个 j，统计左边比它大的

元素个数。对于合并操作是从小到大进行的，当右边的 A[j]复制到 T 中时，左边还没有来

得及复制到 T 的那些数就是左边所有比 A[j]大的数，此时累加器中加上左边元素个数 m-p

即可（左边所剩的元素在区间[p,m]中，因此元素个数为 m-p）。

完整的程序如下：

第 235 页

剩余26页未读，继续阅读

评论收藏

内容反馈

版权申诉

老帽爬新坡

粉丝: 79
资源: 2万+

算法竞赛入门经典授课教案第8章 高效算法设计.doc

算法竞赛入门经典授课教案

算法竞赛入门经典授课教案第4章_函数和递归.doc

算法竞赛入门经典授课教案第4章 函数和递归.doc

算法竞赛入门经典授课教案第7章_暴力求解法.doc

算法竞赛入门经典授课教案第3章 数组和字符串.doc

算法竞赛入门经典授课教案第2章 循环结构程序设计.doc

算法竞赛入门经典授课教案第1章 算法概述.doc

算法竞赛入门经典授课教案第7章 暴力求解法.doc

算法竞赛入门经典授课教案第6章数据结构基础.doc

算法竞赛入门经典各章习题答案.pdf

算法竞赛入门经典第八章代码

算法竞赛入门经典（第二版）3-12章习题+例题 UVa原题

算法竞赛入门经典.pptx

第8章-高效算法设计.doc

算法竞赛入门经典——算法实现.docx

算法竞赛 入门经典 训练指南 代码仓库.7z

算法竞赛入门经典训练指南（高清）.pdf1

《算法竞赛入门经典——训练指南》例题和习题参考代码

全国计算机等级考试二级Python真题及解析.docx

1000份ppt模版，PPT模板优秀PPT

matlab批量读取excel表格数据并处理画图

导入证书可以解决”无法建立到信任根颁发机构的证书链"问题。

OpenCv车辆识别训练模型

代码随想录知识星球精华-大厂面试八股文第二版v1.2.pdf

数学建模对乙醇偶合制备C4烯烃的问题研究

Vue-Element UI集成ECharts实现数据统计分析页代码部分(如果帮助到你，感谢关注点赞)

STM32F103C8T6中文数据手册

（头歌）计算机组成原理存储系统设计（HUST）1-7关答案

MATLAB深度学习入门实例（果树病虫害识别VGG19版）

最新资源

算法竞赛入门经典授课教案第8章高效算法设计.doc

算法竞赛入门经典授课教案第4章函数和递归.doc

算法竞赛入门经典授课教案第3章数组和字符串.doc

算法竞赛入门经典授课教案第2章循环结构程序设计.doc

算法竞赛入门经典授课教案第1章算法概述.doc

算法竞赛入门经典授课教案第7章暴力求解法.doc

算法竞赛入门经典训练指南代码仓库.7z