没有合适的资源?快使用搜索试试~ 我知道了~
第8章-高效算法设计.doc
0 下载量 190 浏览量
2022-12-10
21:27:51
上传
评论
收藏 368KB DOC 举报
温馨提示
试读
23页
第8章_高效算法设计.doc
资源推荐
资源详情
资源评论
第 8 章 高效算法设计
第 231 页
第 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 贪心法
第 8 章 高效算法设计
第 232 页
8.1 算法分析初步
本节介绍算法分析的基本概念和方法,力求在编程之前尽量准确地估计程序的时空开销,
并用出决策。
8.1.1 渐近时间复杂度
例 8-1 最大连续和。
给出一个长度为 n 的序列 A
1
,A
2
,…,A
n
,求最大连续和。换句话说,要求找到 1≤i≤j≤
n,使得 A
1
,A
2
,…,A
n
尽量大。
【分析】
利用枚举思想,可得如下程序:
程序 8-1 最大连续和(1)
tot = 0;
best = A[1]; //初始最大值
for(i = 1; i <= n; i++)
for(j = i; j <= n; j++) { //检查连续子序列 A[i],…,A[j]
int sum = 0;
for(k = i; k <= j; k++) { //累加元素
sum += A[k];
tot++;
}
if(sum > best) best = sum; //更新最大值
}
注意:best 的初值是 A[1],不要写成 best=0。对于本程序中,用 tot 主要是计算加法
运算的次数,它是衡量算法的“工作量”,即“加法”操作的次数。
提示 8-1:统计程序中“基本操作”的数量,可以排除机器速成度的影响,衡量算法本
身的优劣程度。
可以将“加法操作”作为基本操作,也可以将其他四则运算、比较运算作为基本运算。
下面来计算 tot 在一般情况的值,设输入规模为 n 时加法操作的次数为 T(n),则:
1 1
( 1)( 2) ( 1)( 2)
( ) ( 1)
2 6
n n n
i j i i
n i n i n n n
T n j i
= = =
- + - + + +
= - + = =
å å å
可以用一个记号来表示:T(n)=Θ(n
3
),或者说:T(n)与 n
3
同阶。
提示 8-2:基本操作的数量往往可以写成关于“输入规模”的表达式,保留最大项并忽
略系数后的简单表达式称为算法的渐近时间复杂度,它用于衡量算法中基本操作数随规模的
增长情况。
提示 8-3:渐近时间复杂度忽略了很多因素,因而分析结果只能作为参考,并不是精确
的。尽管如此,如果成功抓住了最主要的运算量所在,算法分析的结果常常十分有用的。
8.1.2 上界分析
下面介绍另外一种推导方法:算法包含 3 重循环,内层最坏情况下需要循环 n 次,中层
循环最坏情况下也需要 n 次,外层循环最坏情况下仍然需要 n 次,因此总运算次数不超过 n
3
。
这就是“上界分析。上界也有记号:T(n)=O(n
3
)。
提示 8-4:在算法设计中,常常不进行精确分析,而是假定各种最坏情况同时取到,得
到上界。在很多情况下,这个上界和实际情况同阶(称为“紧”的上界),但也有可能会因
为分析方法不够好,得到“松”的上界。
下面来优化这个算法。设 S
i
=A
1
+A
2
+…+A
i
,则 A
i
+A
i+1
+…+A
j
=S
j
-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){
第 8 章 高效算法设计
第 233 页
best = S[j] - S[i-1];
tot++;
}
}
注意:上面的程序用到了递推的思想:从小到大依次计算 S[1],S[2],S[3]…,每个只需
要在前一个的基础上加上一个元素。换句话说,“计算 S”的步骤的时间复杂度为 O(n)。接
下来是一个二重循环,用类似的方法可以分析出:
1
( 1)
( ) ( 1)
2
n
i
n n
T n n i
=
+
= - + =
å
同样地,用上界分析可以更快地得到结论:内层循环最坏情况下要执行 n 次,外层也是,因
此时间复杂度为 O(n
2
)。
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);
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 正确对待算法分析结果
第 8 章 高效算法设计
第 234 页
对于“最大连续和”问题,先后介绍了时间复杂度 O(n
3
)、O(n
2
)、O(nlogn)的算法,每
个新算法较前一个算法来说,都有是重大的改进。尽管分治法看上去很巧妙,它并不是最高
效的。把 O(n2)算法稍作修改,便可以得到一个 O(n)算法:当 j 确定时,“S[j]-S[i-1]最
大”相当于“S[i-1]最小”,因此只需要扫描一次数组,维护“目前遇到过的最小 S”即可。
把 渐 近 时 间 复 杂 度 为 多 项 式 的 算 法 称 为 多 项 式 时 间 算 法 ( polymonial-time
algorithm),也称为有效算法;而 n! 或 者 2
n
这样的低效的算法称为指数时间算法
(exponential-time algorithm)。
不过需要注意的是,上界分析的结果在趋势上能反映算法的效率,但有两个不精确性:
一是公式本身的精确性;二是对程序实现细节与计算机硬件的依赖性。
8.2 再谈排序与检索
8.2.1 归并排序
第一种高效排序算法是归并排序。按照分治三步法,对归并排序算法介绍如下:
(1)划分问题:把序列分成元素个数尽量相等的两半;
(2)递归问题:把两半元素分别排序;
(3)合并问题:把两个有序表合并成一个。
前两部分很容易完成的,关键在于如何把两个有序表合并成一个。图 8-2 演示了一个合
并的过程。每次只需要把两个序列的最小元素加以比较,删除其中的较小元素并加入合并后
的新表即可。由于需要一个新表来存放结果,所以附加空间 n。
图 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 逆序对数。
第 8 章 高效算法设计
第 235 页
给一列 a
1
,a
2
,…,a
n
,求它的逆序对数,即有多少个有序对(i,j),使得 i<j 但 a
i
>a
j
。n
可以高达 10
6
。
【分析】
受到归并排序的启发,可以用“分治三步法”来做:
(1)划分问题:把序列分成元素个数尽量相等的两半;
(2)递归问题:统计 i 和 j 均在左边或者均在右边的逆序对个数;
(3)合并问题:统计 i 在左边,但 j 在右边的逆序对个数。
解决本问题的关键在于合并:如何求出 i 在左边,而 j 在右边的逆对序对数目呢:按照
j 的不同把这些“跨越两边”的逆序对进行分类:只在对于右边的每个 j,统计左边比它大
的元素个数。对于合并操作是从小到大进行的,当右边的 A[j]复制到 T 中时,左边还没有
来得及复制到 T 的那些数就是左边所有比 A[j]大的数,此时累加器中加上左边元素个数 m-p
即可(左边所剩的元素在区间[p,m]中,因此元素个数为 m-p)。
完整的程序如下:
#include <stdio.h>
int A[] = {8,7,6,5,4,3};
int T[] = {0,0,0,0,0,0};
void inverse_pair(int* A, int x, int y, int* cnt, int* T) {
if(y-x > 1){
int m = x + (y-x)/2; //划分
int p = x, q = m, i = x;
inverse_pair(A, x, m, cnt, T); //递归求解
inverse_pair(A, m, y, cnt, T); //递归求解
while(p < m || q < y) {
if(q >= y || (p < m && A[p] <= A[q])) /从左半数组复制到临时空间
T[i++] = A[p++];
else { //从右半数组复制到临时空间
T[i++] = A[q++];
*cnt += m-p; //计算逆序对数
}
}
for(i = x; i < y; i++) A[i] = T[i]; //从辅助空间复制到 A 数组
}
}
int main(){
int i, cnt = 0;;
inverse_pair(A, 0, 6, &cnt, T);
printf("%d\n", cnt);
return 0;
}
8.2.2 快速排序
快速排序由 Hoare 于 1962 年提出,相对归并排序来说不仅速度更快,并且不需要辅助
空间。按照分治三步法,将快速排序算法作如下介绍。
(1)划分问题:数组的各个元素重排后分成左右两部分,使得左边的任意元素都小于
或等于右边的任意元素。
(2)递归问题:把左右两部分分别排序;
(3)合并问题:不用合并,因为此时数组已经完全有序。
例 8-3 第 k 小的数。
输入 n 个整数和一个正整数(1≤k≤n),输入这些整数从小到大排序后的第 k 个(例如,
k=1 就是最小值)。n≤10
7
。
剩余22页未读,继续阅读
资源评论
java程序员劝退师
- 粉丝: 77
- 资源: 110
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于JavaScript的访客预约系统设计源码
- 基于Vue和ECharts的工作租房数据可视化系统设计源码
- 1040g0cg310ravpiu6ibg5pg00tsipsln3ju2d0g 2
- 基于Python的SAR图像去噪CNN-NLM设计源码
- redhat6升级到redhat7,过程redhat6.x-> redhat6.10->rehat7.9 主版本最高版本
- 基于Django的流程引擎设计源码
- 基于Node.js的Express框架与MySQL的后台管理系统设计源码
- 基于Java的Flink流批一体数据处理快速集成开发框架设计源码
- FirstFilterOrderCompare
- Screenshot_2024-03-28-19-17-25-020_com.ss.android.lark.jpg
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功