4.5 小酌算法分析
关于算法分析其实是一个偏后期的话题，相对于之前介绍的内容这一部分较为抽象，在这里我们只对其进行一些简单的理论介绍。本书中不管是示例的程序还是练习的程序，规模都非常小，每次运行的时候都是很快就出现结果，有些时候甚至是“秒出”，这是因为现在计算机技术的快速发展，即使是个人计算机也有着相对可观的计算能力，但是，这并不能改变运行程序时会消耗资源的事实。
在实际编程中，不管是设计还是应用一种算法，我们都要了解这种算法的性能如何。通常在衡量一个算法的性能时关心的是对CPU和内存的使用效率，但是由于CPU是计算机中最为珍贵的资源，我们还是以CPU的使用率为主，它体现在算法上便是算法的运算速度，用一个专业的词便是算法的时间复杂度。相应地，如果是估计程序需要的存储空间，要考虑的便是空间复杂度。
4.5.1 时间复杂度
由于不能对每个算法都上机测试，我们使用算法中语句的执行次数对算法进行估算，哪个算法中语句执行次数多，它花费时间就多。同时，我们将算法中的语句执行次数称为时间频度，记为T(n)，其中n表示语句的规模。
有了T(n)之后，又出现一个问题，我们不知道随着处理数据量的增长它的变化会呈现出什么规律，因此引入辅助函数f(n)的概念，它和T(n)是同一量级的，同时，使用符号O（f(n)）来替代T(n)，O（f(n)）这种形式也被称为O表示法。这样我们就可以使用函数分析的手段较为准确地分析时间频度T（n），并以此来计算时间复杂度。
4.5.2 O表示法的简单规则
由于有些运行处理对于当前算法来说影响太小了，我们对其选择忽略，具体的规则如下：
（1）常数项使用O(1)表示。
（2）高阶因子和低阶因子并存，只保留高阶因子。
（3）如果最高阶项存在并且不是常数项，则去除它的系数。
对于上述的这些规则下面使用一些代码段进行详细分析。
4.5.3 算法分析示例
常阶数例子：
上述一共4条语句，但是根据规则（1），它的时间复杂度为O(1)，我们称之为常阶数项。具体来说，因为每条语句规模都是常数级的，这决定了它们整体是常数级的，就算有10条，100条这样的语句也是常数级的，时间复杂度不会变。
线性阶例子：
因为循环体中的时间复杂度为O(1)的代码执行了n次，这段代码的规模是由n的个数决定的，因此，它的时间复杂度为O(n)。
平方阶例子：
由于这段代码中内层循环的次数是由外层决定的，因此，它的时间复杂度不能简单地设为n2，但是我们可以对其推导，代码中的输出语句执行次数为：n+(n-1)+(n-2)+(n-3)+…+1。用等差数列求和得到其值为n²/2+n/2。根据规则（2）和规则（3）可得时间复杂度为O(n2)。
4.5.4 常见复杂度及其比较
下面来看看常见的算法复杂度及其例子，具体内容如表4.3所示。
表4.3 常用的算法复杂度
当我们得到一个已知的情况的算法复杂度O（f(n)）时，使用数学曲线即可对其进行分析，假设现在要对两种已知的算法复杂度O（n2）和O（n lgn）进行分析，其中自变量为n也就是算法的规模，因变量为O（f(n)）或是T（n），先来看它们的函数曲线图，如图4.6所示。
图4.6 算法对应辅助函数曲线图
通过图4.6可以看到，问题规模（横轴数据）在0～20时，复杂度O(n2)会远大于O(n lg n)，因此，如果其他情况相同，我们选择复杂度为O(n lg n)的算法。