本书主要取材于算法设计与分析领域的经典内容,并介绍了算法设计的发展趋势。内容主要包括非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些**的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及*新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。本书包括大量的问题实例,并给出了相应的设计与分析方法,书后精选了一些习题,供读者练习,以巩固所学的算法。工业应用领域的许多实际问题和疑难问题都需要有效的求解算法,本书提供于设计有效算法的基础以及大量的可供选择的解决途径。
本书内容基本上涵盖了目前程序设计竞赛所要掌握的算法,并在书后精选了部分ACM国际大学生程序设计竞赛的题目,供大家练习。
本书可作为计算机科学系、数学系、软件学院等专业本科及研究生课程的教材,特别适合于有志于参加程序设计竞赛的学生学习和训练。

第1章 入门
1.4 算法的效率
对于给定的问题,起初只是考虑只要找到一个算法解决该问题就行,而不管该算法花多长时间或者占用多大的存储空间。随着计算机技术的发展,人们发现,求解同一个问题的不同的算法,所需要的运行时间是不同的。例如对排序问题,除了上面介绍过的插入排序算法,我们还将介绍选择排序、合并排序以及快速排序算法。我们自然会问,哪个排序算法好呢?怎么样评价一个算法的好坏呢?这就涉及到算法的时间和空间资源的分析,即算法效率(Efficiency)的分析。
算法效率的分析,指的是算法求解一个问题所需要的时间和空间。分析一个算法,意味着预测该算法解一个问题时,需要花费多少时间和空间资源。空间资源一般指解决一个问题,需要多大的内存、硬盘空间等来存储输入输出数据等。时间资源一般指的是解决一个问题需要多长的时间。一般地,对一个问题,存在不同的求解算法,我们可以根据算法所需要的时空资源来确定出其中有效的算法。随着计算机硬件技术的发展,现在计算机的内存和硬盘空间基本上能满足问题的需要,即空间资源已经不是问题,因此,我们分析一个算法,主要考虑算法的计算时间,今后,我们也主要从时间资源方面对算法进行分析,即分析算法有多快。
在分析一个算法前,我们需要知道如何实现一个算法,这就涉及到计算模型的概念。如果对一个问题,利用计算模型能够实现一个求解算法,则该问题是可解的,否则是不可解的。排序问题是一个可解的问题,因为我们已经找到了许多排序算法。对于不可解的问题,由于无法找到其求解算法,对其进行算法研究也就没必要,本书探讨可解问题的算法设计与分析。
……

第1章 入门
1.1 问题
1.2 算法的概念
1.3 算法的正确性
1.4 算法的效率
1.5 问题的下界
1.6 小结
习题
实验题
第2章 渐近符号
2.1 符号
2.2 符号
2.3 符号
2.4 渐近符号的性质
2.5 常用函数的直观含义
2.6 小结
习题
第3章 算法分析方法
3.1 概率分析
3.2 分摊分析
3.2.1 合计方法
3.2.2 记账方法
3.2.3 势能方法
3.3 实验分析
3.4 小结
习题
第4章 递归
4.1 算法思想
4.1.1 递归算法的应用
4.1.2 递归与迭代
4.2 递归方程的求解
4.2.1 替换方法
4.2.2 递归树方法
4.2.3 公式法
4.3 多项式求值实验
4.4 小结
习题
实验题
第5章 分治算法
5.1 算法思想
5.2 合并排序
5.3 快速排序
5.4 大整数乘法
5.5 矩阵乘法
5.6 残缺棋盘游戏
5.7 快速傅里叶变换(FFT)
5.8 小结
习题
实验题
第6章 动态规划
6.1 算法思想
6.2 装配线调度问题
6.3 矩阵链乘法问题
6.4 *长公共子序列问题
6.5 0/1背包问题
6.6 *优二叉搜索树问题
6.7 动态规划的基本性质
6.8 小结
习题
实验题
第7章 贪心算法
7.1 算法思想
7.2 任务选择问题
7.3 背包问题
7.4 哈夫曼编码问题
7.5 缓存维护问题
……
第8章 图算法
第9章 网络流与匹配
第10章 线性规划
第11章 NP完全理论
第12章 回溯
第13章 分支限界
第14章 启发式搜索
第15章 数论
第16章 计算几何
参考文献