第1章　算法分析

从一般性的复杂研究到特定的分析结果，对计算机算法性质的数学研究已经得到广泛应用。在本章，我们的目标是：为读者提供学习不同算法方法的视角，将我们研究的领域置于相关领域之中，并为本书的剩余部分做铺垫。为此，我们阐述了一个基础且具有代表性的问题领域概念，即排序算法的研究。

首先，我们需要思考进行算法分析的一般动机。为什么要分析一个算法？这样做有什么好处？怎样简化这个过程？然后，我们讨论算法理论，并以归并排序（Mergesort算法）作为示例，它是一种“最优”排序算法。接下来，我们以快速排序（Quicksort算法）为例，看看算法分析包含哪些方面的内容。这包括对基本快速排序算法的各种改进性研究，并通过一些示例说明算法如何帮助调整参数以提高性能。

这些示例反映了对离散数学某些领域背景的明确需要。第2章到第4章介绍了递归、母函数和渐近，这些是算法分析所需的基本数学概念。第5章介绍了符号化方法（symbolic method），这是一个将本书大部分内容联系在一起的标准化方法。第6章到第9章研究基本算法和数据结构的基本组合学特性。因为计算机科学应用的基本方法和经典数学分析之间有密切联系，所以本书同时参考了这两个领域的介绍资料。