1.6　算法分析

一个好的算法往往可以使程序尽可能快地运行，衡量一个算法的好坏，通常将算法效率和存储空间作为重要依据。算法的效率需要通过算法思想编写的程序在计算机上的运行时间来衡量，存储空间需要通过算法在执行过程中所占用的最大存储空间来衡量。

1.6.1　算法设计的4个目标

一个好的算法应该具备以下目标。

1．正确性

算法的正确性（Correctness）是指算法至少应该包括对于输入、输出和处理无歧义性的描述，能正确反映问题的需求，且能够得到问题的正确答案。

通常算法的正确性包括以下4个层次：

（1）算法对应的程序没有语法错误。

（2）对于几组输入数据能得到满足规格要求的结果。

（3）对于精心选择的典型的、苛刻的带有刁难性的几组输入数据，能得到满足规格要求的结果。

（4）对于一切合法的输入都能得到满足要求的结果。

对于这4个层次算法正确性的含义，达到第4个层次的正确是极为困难的，不同输入数据的数量大得惊人，逐一验证的方法是不现实的。一般情况下，我们把第3个层次作为衡量一个程序是否正确的标准。

2．可读性

算法主要是为了人们方便阅读和交流，其次才是计算机执行。可读性（Readability）好有助于人们对算法的理解，晦涩难懂的程序往往隐含着不易被发现的错误，难以调试和修改。

3．健壮性

当输入数据不合法时，算法应该能做出反应或进行处理，而不会产生异常或莫名其妙的输出结果。例如，求一元二次方程ax²+bx+c=0的根的算法，需要考虑多种情况，先判断b²-4ac的正负，若为正数，则该方程有两个不同的实根；若为负数，则表明该方程无实根；若为零，则表明该方程只有一个实根；若a=0，则该方程变成一元一次方程，此时若b=0，则还要处理除数为零的情况。若输入的a、b、c不是数值型，则还要提示用户输入错误。

4．高效率和低存储量需求

效率指的是算法的执行时间。对于同一个问题，如果有多个算法能够解决，那么执行时间短的算法效率高，执行时间长的算法效率低。存储量需求是指算法在执行过程中需要的最大存储空间。效率与存储量需求都与问题的规模有关，求100个人的平均分与求1000个人的平均分所花费的执行时间和运行空间显然有一定差别。设计算法时应尽量选择高效率和低存储量需求的算法。

1.6.2　算法效率评价

算法的执行时间通过依据该算法编制的程序在计算机上运行时所耗费的时间来度量，而度量一个算法在计算机上的执行时间通常有如下两种方法。

1．事后统计

目前计算机内部大都有计时功能，有的甚至可精确到毫秒级，不同算法的程序可通过一组或若干组相同的测试程序和数据来分辨算法的优劣。但是，这种方法有两个缺陷：一是必须依据算法事先编制好程序，这通常需要花费大量的时间与精力；二是时间的长短依赖于计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。因此，人们常常采用事前分析估算的方法来评价算法的好坏。

2．事前分析估算

事前分析估算是指在计算机程序编制之前，对算法依据数学中的统计方法进行估算。这个方法可行的主要原因在于，算法程序在计算机上的运行时间取决于以下因素：

·　算法采用的策略、方法。

·　编译产生的代码质量。

·　问题的规模。

·　书写的程序语言，对于同一个算法，语言级别越高，执行效率越低。

·　机器执行指令的速度。

在以上5个因素中，算法采用不同的策略、不同的编译系统、不同的语言实现、不同的机器运行，效率都不相同。抛开以上因素，算法效率可以通过问题的规模来衡量。

一个算法由控制结构（顺序结构、分支结构和循环结构）和基本语句（赋值语句、声明语句和输入输出语句）构成，算法的运行时间取决于两者执行时间的总和，所有语句的执行次数可以作为语句的执行时间的度量。语句的重复执行次数称为语句频度（Frequency Count）。

例如，斐波那契数列的算法和语句的频度如下：

每一条语句的右端是对应语句的频度，即语句的执行次数。上面算法总的执行次数为f(n)=1+1+1+n+4(n-1)=5n-1。

1.6.3　算法的时间复杂度

算法分析的目的是看设计的算法是否具有可行性，并尽可能挑选运行效率较高的算法。

1．什么是算法的时间复杂度

在进行算法分析时，语句总的执行次数f(n)是关于问题规模n的函数，可以分析f(n)随n的变化情况并确定f(n)的数量级。算法的时间复杂度也就是算法的时间量度，记作T(n)=O(f(n))。

它表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复杂度，记作T(n)。其中，f(n)是问题规模n的某个函数。

一般情况下，随着n的增大，T(n)增长较慢的算法为最优的算法。例如，在下列3个程序段中，给出基本操作x=x+1的时间复杂度分析。

程序段1：

     x=x+1;

程序段2：

     for(i=1;i<n+1;i++)
             x=x+1;

程序段3：

程序段1的时间复杂度为O(1)，称为常量阶；程序段2的时间复杂度为O(n)，称为线性阶；程序段3的时间复杂度为O(n²)，称为平方阶。此外，算法的时间复杂度还有对数阶O(log₂n)、指数阶O(2ⁿ)等。

斐波那契数列的时间复杂度T(n)=O(n)。

常用的时间复杂度所耗费的时间从小到大依次是O(1)<O(log₂n)<O(n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)。

算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下，具有指数级的时间复杂度的算法只有当n足够小时才是可使用的算法。具有常量阶、线性阶、对数阶、平方阶和立方阶的时间复杂度的算法是常用的算法。一些常见函数的增长率如图1-12所示。

一般情况下，算法的时间复杂度只需要考虑关于问题规模n的增长率或阶数。例如以下程序段：

语句k++的执行次数关于n的增长率为n²，它是语句频度(n-1)(n-2)/2中增长最快的项。

在某些情况下，算法的基本操作的重复执行次数不仅依赖于输入数据集的规模，还依赖于数据集的初始状态。例如，在以下的冒泡排序算法中，其基本操作执行次数还取决于数据元素的初始排列状态：

交换相邻的两个整数为该算法中的基本操作。当数组a中的初始序列为从小到大排序的有序排列时，其基本操作的执行次数为0；当数组中的初始序列从大到小排列时，其基本操作的执行次数为n(n-1)/2。对这类算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度；另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。若数组a中的初始输入数据可能出现n!种排列情况的概率相等，则冒泡排序的平均时间复杂度为T(n)=O(n²)。

然而，在很多情况下，各种输入数据集出现的概率难以确定，算法的平均时间复杂度也就难以确定。因此，另一种更可行，更常用的办法是讨论算法在最坏情况下的时间复杂度，即分析最坏情况以估算算法执行时间的上界。例如，上面的冒泡排序的最坏时间复杂度为数组a中的初始序列为从大到小有序，则冒泡排序算法在最坏情况下的时间复杂度为T(n)=O(n²)。一般情况下，本书以后讨论的时间复杂度，在没有特殊说明的情况下，指的是最坏情况下的时间复杂度。

2．算法的时间复杂度分析举例

一般情况下，算法的时间复杂度只需要考虑算法中的基本操作，即算法中最深层语句的操作。

【例1-1】分析以下程序段的时间复杂度。

该程序段中的基本操作是内层for循环中的语句，即x=x+1和a[i][j]=x，其语句频度为(n-1)(n-2)/2。因此，其时间复杂度为O(n²)。

【例1-2】分析以下算法的时间复杂度。

函数Fun()的基本运算是i=i*2，设执行次数为f(n)，2^f(n)≤n，则有f(n)≤log₂n。因此，时间复杂度为O(log₂n)。

【例1-3】分析以下算法的时间复杂度。

该算法中的基本操作是while循环中的语句，设while循环次数为f(n)，则变量i从0到f(n)，循环次数为f(n)*(f(n)+1)/2≤n，，故时间复杂度为。

【例1-4】一个算法所需的时间由以下递归方程表示，分析算法的时间复杂度。

根据以上递归方程，可得：

因此，该算法的时间复杂度为O(2ⁿ)。

1.6.4　算法的空间复杂度

空间复杂度（Space Complexity）作为算法所需存储空间的量度，记作S(n)=O(f(n))。其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占存储空间只取决于问题本身，和算法无关，则只需要分析该算法在实现时所需的辅助空间即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。

【例1-5】以下是一个简单的插入排序算法，分析算法的空间复杂度。

该算法借助了变量t，与问题规模n的大小无关，空间复杂度为O(1)。

【例1-6】以下算法是求n个数中的最大者，分析算法的空间复杂度。

设FindMax(a,n)占用的临时空间为S(n)，由以上算法可得到以下占用临时空间的递推式。

则有S(n)=S(n-1)+1=S(n-2)+1+1=…=S(1)+1+1+…+1=O(n)。因此，该算法的空间复杂度为O(n)。