算法设计与分析

● 紧扣教学规律，合理设计内容结构。

● 让读者掌握现今流行技术的底层算法及复杂度分析。

● 提供电子课件等资源，方便教学。

党的二十大报告明确提出，教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，开辟发展新领域新赛道，不断塑造发展新动能新优势。要坚持教育优先发展、科技自立自强、人才引领驱动，加快建设教育强国、科技强国、人才强国，坚持为党育人、为国育才，全面提高人才自主培养质量，着力造就拔尖创新人才，聚天下英才而用之。

在面临经济发展转型、科学技术“卡脖子”等问题的背景下，高等教育的重点是加强基础学科、新兴学科、交叉学科建设，加快建设优势学科。计算机科学与技术学科紧跟国内外计算机科学与技术前沿，为国家培养计算机科学与技术高层次人才，而计算机科学与技术专业是一个计算机系统与网络兼顾的计算机学科宽口径专业，旨在培养具有良好的科学素养、具有自主学习意识和创新意识、科学型和工程型相结合的计算机专业高水平工程技术人才。

“算法设计与分析”是计算机科学与技术专业的核心课程，它将高级语言程序设计、数据结构和计算方法等内容紧密地结合在一起，通过介绍常见的算法设计策略、复杂性分析方法和应用，培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，为学生开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。

本书将社会上比较流行的、比较先进的部分互联网技术进行分析，挖掘其底层借鉴的基本算法，让读者掌握现今流行技术的底层算法及复杂度分析，提高读者的学习积极性及主动性，培养读者积极探索的科学精神。

全书共分7章：

第1章 算法概述。简单介绍了算法的概念，算法与程序的区别与联系，算法的时间复杂度和空间复杂度分析。

第2章 递归。通过实例介绍了递归方程的设计方法，同时给出求解递归方程的方法。

第3章 分治法。介绍了分治法的基本思想，并通过二分搜索、棋盘覆盖、合并排序、快速排序等应用详细介绍分治法的设计思想、时间复杂度分析。

第4章 动态规划。先由几个实例引出动态规划算法的基本思想及求解过程，然后分析了备忘录方法与动态规划算法的异同，并通过最长公共子序列、最大子段和、合唱队形问题、0-1背包问题详细介绍动态规划算法的设计方法、时间复杂度分析。

第5章 贪心算法。通过实例分析了贪心算法的设计思想、基本要素，并通过活动安排问题、背包问题、最优装载问题、哈夫曼编码等应用详细给出贪心策略的设计方法、贪心策略的证明。

第6章 回溯法。本章首先介绍解空间的基本概念，并给出构造解空间的过程分析，然后介绍回溯法的框架，并通过装载问题、n后问题、0-1背包问题等详细介绍回溯法的构造过程，最后分析了影响回溯法效率的原因。

第7章 分支限界法。本章首先介绍分支限界法与回溯法的异同，然后通过单源最短路径、装载问题、0-1背包问题详细介绍分支限界法的求解步骤。

本书采用C++语言作为表述手段，书中介绍了各种算法的设计思路、算法复杂性及实例分析，同时在每一章的章首部分增加了学习要点，每一章的章末附有和本章内容相关的习题，并免费提供电子课件。

本书的编写得到了齐鲁工业大学计算机科学与技术学部人才培养提升计划优秀教材培育项目的支持，同时得到了齐鲁工业大学教材建设基金资助，在此表示衷心的感谢。

本书由赵晶任主编，尉秀梅、李爱民、鲁芹、姜雪松任副主编，编写过程中的校对工作由硕士生邹庆志、胡玉帅、张荣环、高帅、时俊康、豆希梦、吴栋林、曲相宇、秦宥煊、石明、王浩、张雪峰完成，在此表示感谢。

由于编者的知识和写作水平有限，书稿虽几经修改，仍难免存在缺点和错误，热忱欢迎同行专家和读者惠予批评指正，使本书不断改进，日臻完善。

编 者

2022年6月

第1章 算法概述 1
1.1 算法与程序 1
1.1.1 算法与程序概述 1
1.1.2 为什么要学习算法？ 1
1.1.3 算法的描述方法 2
1.1.4 解决问题的基本步骤 4
1.2 算法的时间复杂度 5
1.2.1 算法设计的例子 5
1.2.2 为什么需要对算法进行复杂度
分析？ 8
1.2.3 算法的复杂度分析 9
1.2.4 算法时间复杂度的定义 11
1.2.5 运行时间的上界（O记号） 13
1.2.6 运行时间的下界（Ω记号） 15
1.2.7 运行时间的准确界（Θ记号） 16
1.3 算法的空间复杂度 18
1.4 NP类问题 19
习题 19
第2章 递归 21
2.1 递归算法 21
2.2 求解递归方程 28
2.2.1 迭代法 28
2.2.2 差消法 29
2.2.3 递归树法 30
2.2.4 主定理法 31
习题 34
第3章 分治法 37
3.1 分治法引言 37
3.2 分治法的基本思想 37
3.2.1 基本思想 37
3.2.2 时间复杂度分析 39
3.3 二分搜索 40
3.3.1 寻找假币 40
3.3.2 二分搜索问题 42
3.4 棋盘覆盖 44
3.5 合并排序 47
3.6 快速排序 51
3.7 金块问题 53
3.8 循环赛日程表 56
习题 58
第4章 动态规划 63
4.1 几个实例 63
4.1.1 爬楼梯问题 63
4.1.2 国王挖金矿问题 64
4.1.3 矩阵连乘问题 65
4.2 动态规划算法的基本思想 67
4.2.1 动态规划算法的特征 67
4.2.2 动态规划算法求解过程 68
4.3 备忘录方法 71
4.4 最长公共子序列 71
4.4.1 最长公共子序列问题 71
4.4.2 所有最长公共子序列 76
4.5 最大子段和 79
4.6 合唱队形问题 83
4.7 0-1背包问题 85
习题 90
第5章 贪心算法 93
5.1 贪心算法引言 93
5.1.1 贪心算法实例 93
5.1.2 贪心算法的设计思想 95
5.2 活动安排问题 96
5.3 贪心算法的基本要素 99
5.4 两种不同的背包问题 100
5.4.1 0-1背包问题 100
5.4.2 背包问题 101
5.5 最优装载问题 103
5.6 哈夫曼编码 104
5.7 单源最短路径 112
5.8 最小生成树 118
5.8.1 最小生成树性质 119
5.8.2 Prim算法 119
5.8.3 Kruskal算法 122
5.9 多机调度问题 123
习题 126
第6章 回溯法 128
6.1 回溯法引言 128
6.2 回溯法的基本思想 129
6.2.1 问题的解空间 129
6.2.2 基本思想 132
6.2.3 构造解空间的过程 133
6.3 回溯法框架 137
6.3.1 递归回溯 137
6.3.2 迭代回溯 138
6.3.3 子集树 138
6.3.4 排列树 139
6.4 装载问题 140
6.5 n皇后问题 146
6.6 0-1背包问题 151
6.7 高逐位整除数 157
6.8 图的m着色问题 159
6.9 回溯法效率分析 163
习题 164
第7章 分支限界法 165
7.1 分支限界法的基本思想 165
7.1.1 分支限界法与回溯法的异同 165
7.1.2 分支限界法求解步骤 166
7.1.3 常见的两种分支限界法 167
7.2 单源最短路径问题 178
7.3 装载问题 181
7.4 0-1背包问题 187
习题 192
参考文献 194

1. 输水管线工程风险管理 [张勇 党亥生 著]
2. 民用航空飞机标准线路施工 [主编　王志敏　陈明]
3. 不息的水脉—大运河讲谈录 [赵珩　著]
4. 实用运筹学 [主编　邢育红　于晋臣]
5. 三峡梯级电站水资源决策支持系统研究与开发 [姚华明 潘红忠 汤正]
6. 海南黎族民俗文化鉴赏 [庞国华　著]
7. 石墨烯在太赫兹及中红外频段电磁器件设计中的应用 [李艳秀 庄华伟 著]
8. 电子技术（第二版） [主编 覃爱娜 李飞]
9. 办公自动化高级应用 [陈萍 朱晓玉]
10. 信息处理技术员考试32小时通关 [薛大龙]
11. 电子产品设计案例教程（微课版）—基于嘉立创EDA（专业版） [王静 莫志宏 陈学昌 丁红]
12. C程序设计实践教程 [刘卫国]
13. C程序设计（慕课版） [刘卫国]
14. Web技术开发教程（基于.NET开源MVC框架） [王合闯 韩红玲 王青正 陈海蕊]
15. 商务英语翻译教程（笔译）（第四版） [主编 王军平]
16. 智慧零售技术与应用 [洪旭 著]
17. 建设工程法规实务 [主编 余滢]
18. 商务秘书理论与实务（第三版） [主编 张同钦]
19. 程序设计基础实践教程（C/C++语言版） [张桂芬 葛丽娜]
20. C++案例项目精讲 [主编 杨国兴]
21. 劳动争议处理实务 [主编 王秀卿 罗静]
22. 工程数学 [主编 郭立娟 王海]
23. 语音识别理论与实践 [主编　莫宏伟]
24. 信息系统项目管理师章节习题与考点特训（第二版） [主编 薛大龙]
25. 武术基础教程 [主编 李代勇 谢志民]
26. 计算机网络实训教程 [主编 张浩军 赵玉娟]
27. 画法几何与机械制图习题集（多学时） [主编 赵军]
28. HCIA-Datacom认证题库分类精讲 [主 编 韩立刚]
29. SwiftUI完全开发 [李智威 著]
30. 网络规划设计师备考一本通 [夏杰 编著]