算法效率分析基础
本章主要讨论算法分析。美国传统辞典(The American Heritage Dictionary)将“分析”定义为“将知识或物质的整体细分成组成部分进行个体研究”。1.2节指出的算法的每种主要特性都值得研究。但是“算法分析”仅用于对算法运行时间和存储空间的效率做定义。因为和简单性，一般性这样的特性不同，对效率是可以做精确的定量研究。
2.1节以一个算法效率研究的通用框架开始。它讲述的主题和基本原理有关，也是本书最重要的节之一。
在2.2节，我们介绍了三种符号：Ο(读作”O”), Ω(读作”omega”), Θ(读作”theta”).这些讨论算法效率的特定语言。
2.3节显示了如何使用2.1节所介绍的通用框架系统地对非递归算法进行分析。这种分析的主要工具是先定义一个代表算法运行时间的求和表达式，然后使用标准的求和法制对表达式进行化简。
2.4节显示了用2.1节所介绍的通用框架，系统地分析递归算法。主要的分析工具是一种称为递推关系的特殊等式。我们应先建立递推关系，然后介绍一种对其求解的方法。
前4节用了很多例子讲解分析框架和该框架的应用，2.5节介绍另外一个例子——斐波那契数列。引入斐波那契数列是将它作为一种研究工具应用于2.4节的方法所不能解决的一类重要递推关系，讨论几种计算斐波那契数的算法。
2.3节和2.4节的方法，以数学的方式分析算法的效率，但并非简单好用。本章的最后两节讨论另外一种方法——经验分析和算法可视法，弥补纯数学方法的不足。
分析框架概要
我们对分析框架作一个总结。
- 算法的时间效率和空间效率都用输入规模的函数进行度量。
- 我们用算法基本操作的执行次数来度量算法的时间效率。通过计算算法消耗的额外存储单元的数量来度量空间效率。
- 在输入规模相同的情况下，有些算法的效率会有显著差异。对于这样的算法，我们需要区分最差效率，平均效率和最优效率。
- 本框架主要关心，当算法的输入规模趋向于无限大的时候，其运行时间（消耗的额外空间）函数的增长次数。
2.2节研究增长次数的正式方式。在2.3节和2.4节，分别讨论了非递归算法和递归算法的特殊研究方法。这3节会应用2.1节描述的分析框架来研究特定算法的效率。
小结
- 有两种算法效率：时间效率和空间效率。时间效率指出算法运行得有多快；空间效率涉及算法需要得额外空间。
- 算法的时间效率主要用它输入规模的函数来度量，该函数计算算法基本操作的执行次数。基本操作是在总运行时间中贡献最大的操作。通常，它是算法的最内层循环中最费时的操作。
- 对于有些算法来说，对于相同规模的输入，它的运行时间会有相当大的不同，导致了最差效率，平均效率和最优效率等概念的产生。
- 当算法的输入规模趋向于无穷大时，算法的运行时间表现出固定的增长次数。我们建立的分析算法时间效率的框架，主要就是基于这个增长次数。
- 符号O, Ω和Θ能够指出算法效率的渐进增长次数，也呢过对不同的函数进行比较。
- 大多数算法的效率可以分为以下几类：常数，对数，线性，”n-log-n”,平方，立方和指数。
- 分析非递归算法时间效率的主要工具是建立算法的基本操作执行次数的求和表达式，然后确定“和函数”的增长次数。
- 分析递归算法时间效率的主要工具是建立算法的基本操作执行次数的递推关系式，然后确定它的增长次数。
- 递归算法的简洁性可能掩盖它的低效率。
- 斐波那契数是一种重要的整数序列，它的每一个元素值都等于最近的两个前趋的和。有许多计算斐波那契数的算法，它们的效率有很大的不同。
- 算法的经验分析是针对一个输入样本，运行算法的一个程序实现，然后分析观测到的数据（基本操作次数或物理运行时间）。这常常涉及到生成伪随机数。这种方法的主要优点是可以应用于任何算法；它的主要缺点是要依赖于特定的计算机和输入样本。
- 算法可视法是利用图像来传达有关算法的有用信息。算法可视法的两个主要变种是静态算法可视法和动态算法可视法（也称为算法动画）。