算法设计与分析

David Berlinski在The Advent of the Algorithm中写道： 有两种思想，像珠宝商放在天鹅绒上的宝石一样熠熠生辉，一个是微积分，另一个就是算法。微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学，而算法则造就了现代世界。算法是当代信息技术的重要基石，同时也是计算科学的永恒主题。在计算机科学技术领域，算法更是处于核心地位。通过对算法系统的学习和研究，掌握算法设计的主要方法，能够正确分析算法的复杂性。这对每一位从事计算机系统结构、系统软件、应用软件研究和开发的科技人员都是非常重要和必不可少的。本书是在结合编者多年教学经验及实践的基础上编写而成的，详细讲述了多种经典算法设计策略。纵观全书，这里并没有创造出任何新的算法，因为编者仅仅是希望通过对经典算法的讲解，把算法设计与分析中基础且重要的内容用更清晰的思路、更直观的形式展现给读者。
本书主要内容
本书以算法策略为知识单元，共9章内容，其中第1章是算法概述，第2~8章是经典的算法设计策略，第9章简单介绍了NP完全理论。
第1章为算法概述。主要介绍了什么是算法、为什么学习算法、算法的描述方式、算法设计的一般过程、算法分析、递推方程求解方法等。
第2章为贪心算法——贪心不足。首先介绍贪心算法的本质、贪心算法的基本要素； 接着从问题分析、算法设计、实例构造、算法分析和Python实战5个方面讲解经典问题，包括活动安排问题、单源短路径问题、哈夫曼编码、小生成树和背包问题等。
第3章为分治算法——分而治之。首先介绍分治算法的本质、分治算法的求解步骤； 接着从问题分析、算法设计、实例构造、算法分析和Python实战5个方面讲解经典问题，包括二分查找、选第二大元素、循环赛日程表、合并排序、快速排序、线性时间选择等。
第4章为动态规划。首先介绍动态规划的基本思想、求解步骤及基本要素； 接着从问题分析、算法设计、实例构造、算法分析和Python实战5个方面讲解经典问题，包括矩阵连乘问题、凸多边形三角剖分、长公共子序列问题、加工顺序问题、01背包问题及二叉查找树等。
第5章为回溯法——深度优先搜索。首先讲解回溯法的算法框架及思想； 然后介绍了典型的解空间结构，讲解用回溯法求解的经典问题，包括01背包问题、团问题、批处理作业调度问题、旅行商问题、图的m着色问题及小质量机器设计问题等。
第6章为分支限界法——宽度优先或小耗费（效益）优先搜索。首先讲解分支限界法的基本思想； 然后讲解用分支限界法求解的经典问题，包括01背包问题、旅行商问题、布线问题； 后对比分析了回溯法和分支限界法的异同点，设计了分支限界法实践，用于巩固分支限界法设计策略。
第7章为线性规划问题与网络流。着重讲述线性规划问题的标准化及单纯形算法、网络流的基本概念及理论、求流的增广路算法、求小费用流的消圈算法，通过线性规划问题与网络流实践巩固相关算法设计思想。
第8章为随机化算法。着重讲述了随机数发生器、数值随机化算法、蒙特卡罗算法、拉斯维加斯算法、舍伍德算法，并结合实例讲述了每种类型随机化算法的特点，通过随机化算法实践巩固随机化算法的设计方法。
第9章为NP完全理论。简单介绍了NP理论和近似算法，以引起读者进一步学习和研究的兴趣。
本书特色
（1） 实例丰富、通俗易懂。针对每一种算法设计策略，通过实例图解算法运行过程，形象直观、通俗易懂。
（2） 完整的实战演练，易于上机操作。针对每个经典问题，在算法设计、实例构造的基础上，提供完整Python代码，学习者可以体验从理论到实践的快感。
（3） 注重算法实践。针对主要算法概念及算法设计策略，精心设计实践内容，便于学习者巩固算法设计与分析的方法。
（4） 网络资源丰富，便于教学、自学。网络资源包括本书所有Python源代码、习题解析、微视频、微课件、随堂测试等丰富的学习资源。
配套资源
为便于教与学，本书配有微课视频、源代码、题库、教学课件、教学大纲、考试试卷、教学进度表、实验指导书等。
（1） 获取教学视频方式： 读者可以先扫描本书封底的文泉云盘防盗码，再扫描书中相应的视频二维码，观看教学视频。
（2） 获取源代码、实验指导书和扩展阅读（数论算法及计算几何算法）方式： 先扫描本书封底的文泉云盘防盗码，再扫描下方二维码，即可获取。

源代码

实验指导书

扩展阅读

（3） 其他配套资源可以扫描本书封底的课件二维码下载。
读者对象
本书面向计算机科学与技术、软件工程、智能科学、数据科学与大数据等计算机类相关专业的教师、学生及广大科研工作者，计算机类算法相关工作的从业人员。
本书的编写参考了诸多相关资料，得到多方面的支持，在此谨向清华大学出版社负责本书编辑出版工作的全体同仁、资料提供者及每一位曾经关心和支持本书编写工作的专家们表示衷心感谢。
限于个人水平和时间仓促，书中难免存在疏漏之处，欢迎读者批评指正。
编者

2021年1月 

本书主讲贪心算法、分治算法、动态规划算法、回溯算法、网络流、随机化算法、近似算法，侧重用具体实例图解演示算法运行过程及python语言实现。本书特色：深入浅出地从问题分析，到数据结构选择、算法设计、Python实战，提供问题解决的全程式指导；提供实例构造、详细图解，带领学习者直观、形象地逐步运行算法，看到算法单步运行结果；提供算法的Python语言实现，让算法在学习者心里落地生根。本书适用于计算机、大数据等相关专业本科教材，以及从事计算机领域的教学、科研人员，ACM程序设计大赛的算法爱好者。

王秋芬，女，1978-，硕士研究生，副教授。研究方向为计算机软件理论、算法、大数据，主讲《操作系统》、《数据结构》、《算法设计与分析》等课程。从教以来，获校级教学技能竞赛一等奖、省级教学技能竞赛二等奖；以作者发表论文20余篇，出版《算法设计与分析》、《算法设计艺术》等3部著作；主持、参与省级项目6项，主持课程与教材建设项目5项；获省部级以上奖励5项；已获授权国家发明专利4项。

第1章算法概述

1.1什么是算法

1.2为什么学习算法

1.3算法的描述方式

1.4算法设计的一般过程

1.5算法分析

1.5.1算法分析的概念

1.5.2时间复杂度和空间复杂度

1.5.3渐近复杂性态

1.5.4渐近意义下的记号

1.5.5算法的运行时间T(n)建立的依据

1.5.6算法所占用的空间S(n)建立的依据

1.6递推方程求解方法

1.6.1迭代法

1.6.2递归树

1.6.3差消法

1.6.4主方法

第2章贪心算法——贪心不足

2.1概述

2.1.1贪心算法的本质

2.1.2贪心算法的基本要素

2.2活动安排问题

2.2.1问题分析——贪心策略

2.2.2算法设计

2.2.3实例构造

2.2.4算法分析

2.2.5Python实战

2.3单源短路径问题

2.3.1问题分析——贪心策略

2.3.2算法设计

2.3.3实例构造

2.3.4算法分析

2.3.5Python实战

2.4哈夫曼编码

2.4.1问题分析——贪心策略

2.4.2算法设计

2.4.3实例构造

2.4.4算法分析

2.4.5Python实战

2.5小生成树——Prim算法

2.5.1问题分析——贪心策略

2.5.2算法设计

2.5.3实例构造

2.5.4算法分析

2.5.5Python实战

2.6小生成树——Kruskal算法

2.6.1问题分析——贪心策略

2.6.2算法设计

2.6.3实例构造

2.6.4算法分析

2.6.5Python实战

2.7背包问题

2.7.1问题分析——贪心策略

2.7.2算法设计

2.7.3实例构造

2.7.4算法分析

2.7.5Python实战

第3章分治算法——分而治之

3.1概述

3.1.1分治算法的本质

3.1.2分治算法的求解步骤

3.2二分查找

3.2.1问题分析——分与治的方法

3.2.2算法设计

3.2.3实例构造

3.2.4算法分析

3.2.5Python实战

3.3选第二大元素

3.3.1问题分析——分与治的方法

3.3.2算法设计

3.3.3实例构造

3.3.4算法分析

3.3.5Python实战

3.4循环赛日程表

3.4.1问题分析——分与治的方法

3.4.2算法设计

3.4.3实例构造

3.4.4算法分析

3.4.5Python实战

3.5合并排序

3.5.1问题分析——分与治的方法

3.5.2算法设计

3.5.3实例构造

3.5.4算法分析

3.5.5Python实战

3.6快速排序

3.6.1问题分析——分与治的方法

3.6.2算法设计

3.6.3实例构造

3.6.4算法分析

3.6.5Python实战

3.7线性时间选择——找第k小问题

3.7.1问题分析——分与治的方法

3.7.2算法设计

3.7.3实例构造

3.7.4算法分析

3.7.5Python实战

第4章动态规划

4.1概述

4.1.1动态规划的基本思想

4.1.2动态规划的求解步骤

4.1.3动态规划的基本要素

4.2矩阵连乘问题

4.2.1问题分析——递归关系

4.2.2算法设计

4.2.3实例构造

4.2.4算法分析

4.2.5Python实战

4.3凸多边形三角剖分

4.3.1问题分析——递归关系

4.3.2算法设计

4.3.3实例构造

4.3.4算法分析

4.3.5Python实战

4.4长公共子序列问题

4.4.1问题分析——递归关系

4.4.2算法设计

4.4.3实例构造

4.4.4算法分析

4.4.5Python实战

4.5加工顺序问题

4.5.1问题分析——递归关系

4.5.2算法设计

4.5.3实例构造

4.5.4算法分析

4.5.5Python实战

4.601背包问题

4.6.1问题分析——递归关系

4.6.2算法设计

4.6.3实例构造

4.6.4算法分析

4.6.5算法的改进

4.6.6Python实战

4.7二叉查找树

4.7.1问题分析——递归关系

4.7.2算法设计

4.7.3实例构造

4.7.4算法分析

4.7.5Python实战

第5章回溯法——深度优先搜索

5.1概述

5.2典型的解空间结构

5.2.1子集树

5.2.2排列树

5.2.3满m叉树

5.301背包问题——子集树

5.3.1问题分析——解空间及搜索条件

5.3.2算法设计

5.3.3实例构造

5.3.4算法的改进

5.3.5算法分析

5.3.6Python实战

5.4团问题——子集树

5.4.1问题分析——解空间及搜索条件

5.4.2算法设计

5.4.3实例构造

5.4.4算法分析

5.4.5Python实战

5.5批处理作业调度问题——排列树

5.5.1问题分析——解空间及搜索条件

5.5.2算法设计

5.5.3实例构造

5.5.4算法分析

5.5.5Python实战

5.6旅行商问题——排列树

5.6.1问题分析——解空间及搜索条件

5.6.2算法设计

5.6.3实例构造

5.6.4算法分析

5.6.5Python实战

5.7图的m着色问题——满m叉树

5.7.1问题分析——解空间及搜索条件

5.7.2算法设计

5.7.3实例构造

5.7.4算法分析

5.7.5Python实战

5.8小质量机器设计问题——满m叉树

5.8.1问题分析——解空间及搜索条件

5.8.2算法设计

5.8.3实例构造

5.8.4算法分析

5.8.5Python实战

第6章分支限界法——宽度优先或小耗费(效益)优先搜索

6.1分支限界法的基本思想

6.201背包问题

6.3旅行商问题

6.4布线问题

6.4.1问题分析——解空间及搜索条件

6.4.2算法设计

6.4.3实例构造

6.4.4算法分析

6.4.5Python实战

6.5分支限界法与回溯法的比较

第7章线性规划问题与网络流

7.1线性规划问题

7.1.1一般线性规划问题的描述

7.1.2标准型线性规划问题的描述

7.1.3标准型线性规划问题的单纯形算法

7.2网络流

7.2.1基本概念

7.2.2增广路算法

7.2.3网络流的变换与应用

7.3小费用流

7.3.1基本概念

7.3.2消圈算法

7.3.3小费用流的变换与应用

第8章随机化算法

8.1概述

8.1.1随机化算法的类型及特点

8.1.2随机数发生器

8.2数值随机化算法

8.2.1计算π的值

8.2.2计算定积分

8.3蒙特卡罗算法

8.3.1主元素问题

8.3.2素数测试

8.4拉斯维加斯算法

8.4.1整数因子分解

8.4.2n皇后问题

8.5舍伍德算法

8.5.1随机快速排序

8.5.2线性时间选择

第9章NP完全理论

9.1易解问题和难解问题

9.2P类和NP类问题

9.2.1P类问题

9.2.2NP类问题

9.2.3P类问题和NP类问题的关系

9.3NP完全问题

9.3.1多项式变换技术

9.3.2典型的NP完全问题

9.4NP完全问题的近似算法

9.4.1顶点覆盖问题

9.4.2装箱问题

9.4.3旅行商问题TSP

9.4.4集合覆盖问题

参考文献

本书主讲贪心算法、分治算法、动态规划算法、回溯算法、网络流、随机化算法、近似算法，侧重用具体实例图解演示算法运行过程及python语言实现。本书特色：深入浅出地从问题分析，到数据结构选择、算法设计、Python实战，提供问题解决的全程式指导；提供实例构造、详细图解，带领学习者直观、形象地逐步运行算法，看到算法单步运行结果；提供算法的Python语言实现，让算法在学习者心里落地生根。本书适用于计算机、大数据等相关专业本科教材，以及从事计算机领域的教学、科研人员，ACM程序设计大赛的算法爱好者。

王秋芬，女，1978-，硕士研究生，副教授。研究方向为计算机软件理论、算法、大数据，主讲《操作系统》、《数据结构》、《算法设计与分析》等课程。从教以来，获校级教学技能竞赛一等奖、省级教学技能竞赛二等奖；以作者发表论文20余篇，出版《算法设计与分析》、《算法设计艺术》等3部著作；主持、参与省级项目6项，主持课程与教材建设项目5项；获省部级以上奖励5项；已获授权国家发明专利4项。