下载掌阅APP，畅读海量书库
立即打开
一个好的算法往往会带来程序运行效率高的好处，算法效率和存储空间需求是衡量算法优劣的重要依据。算法的效率需要通过算法编制的程序在计算机上的运行时间来衡量，存储空间需求通过算法在执行过程中所占用的最大存储空间来衡量。
一个好的算法应该具备以下目标。
算法的正确性是指算法至少应该是输入、输出和加工处理无歧义性，并能正确反映问题的需求，能够得到问题的正确答案。通常算法的正确性应包括以下四个层次：a.算法所设计的程序没有语法错误；b.算法所设计的程序对于几组输入数据能够得到满足要求的结果；c.算法所设计出的程序对于特殊的输入数据能够得到满足要求的结果；d.算法所设计出的程序对于一切合法的输入都能得到满足要求的结果。对于这四层算法正确性的含义，层次d是最困难的，一般情况下，把层次c作为衡量一个程序是否正确的标准。
算法设计的目的首先是人们的阅读、理解和交流，其次才是计算机执行。可读性好有助于人们对算法的理解，晦涩难懂的算法往往隐含错误不易被发现，并且调试和修改困难。
当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。例如，计算一个三角形面积的算法，正确的输入应该是三角形的三条边的边长，如果输入字符类型数据则不应该继续计算，而应该报告输入错误，给出提示信息。
效率指的是算法的执行时间。对于同一个问题如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需求指的是算法在执行过程中需要的最大存储空间。设计算法应尽量选择高效率和低存储量需求的算法。
算法分析的目的是看设计的算法是否具有可行性，并尽可能挑选运行效率高的算法。
衡量一个算法在计算机上的执行时间通常有以下两种方法。
这种方法主要是通过设计好的测试程序和数据，利用计算机的计时器对不同算法编制好的程序比较各自的运行时间，从而确定算法效率的好坏。但是，这种方法有三个缺陷：一是必须依据算法事先编制好程序，这通常需要花费大量的时间与精力；二是时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣；三是算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大的关系，效率高的算法在小的测试数据面前往往得不到体现。
这主要在计算机程序编制前，对算法依据数学中的统计方法进行估算。这主要是因为算法的程序在计算机上的运行时间取决于以下因素：
a.算法采用的策略、方法；
b.编译产生的代码质量；
c.问题的规模；
d.书写的程序语言，对于同一个算法，语言级别越高，执行效率越低；
e.机器执行指令的速度。
在以上五个因素中，算法采用不同的策略，或不同的编译系统，或不同的语言实现，或在不同的机器运行时，效率都不相同。抛开以上因素，仅考虑算法本身的效率高低，可以认为一个算法的效率仅依赖于问题的规模。因此，通常采用事前分析估算方法衡量算法的效率。
抛开硬件因素，问题规模和算法的策略成为影响算法效率的主要因素。问题规模是算法求解问题输入量的多少，是问题大小的表示，一般用整数n表示。对不同的问题，问题规模n有不同的含义。例如，对于矩阵运算，n为矩阵的阶数；对于多项式运算，n为多项式的项数；对于图的有关运算，n为图中顶点的个数。显然，对于同一个问题，n取值越大，算法的执行时间会越长。
算法的时间分析度量标准不是执行实际算法的具体运行时间，而是算法中所有语句的执行时间总和。一个算法由控制结构（顺序、分支和循环结构）和基本语句（赋值语句、声明语句和输入输出语句）构成，则算法的运行时间取决于两者执行时间的总和。一条语句的执行时间等于该条语句的重复执行次数和执行一次语句所需时间的乘积，其中一条语句的重复执行次数称为语句频度（Frequency Count）。而语句执行一次所需时间是与机器的配置、编译程序质量等密切相关的，算法分析并非精确计算算法的实际执行时间，而是对算法的语句执行次数进行估计。对于问题规模为n的语句，其语句频度可表示为f（n），也就是说，算法的执行时间与f（n）成正比。
例如，两个n×n矩阵相乘的算法和语句的频度如下。
每一条语句的最右端是对应语句的频度，即语句的执行次数。上面算法总的执行次数为f（n）=n+n 2 +n 2 +n 3 +n 3 =2n 3 +2n 2 +n。
对于较为复杂的算法来说，语句的频度难以直接表示，或者语句的频度虽可用数学公式表示出来，但可能是一个非常复杂的函数。因此，为了客观反映一个算法的执行时间，通常将算法中的基本操作语句重复执行的频度作为度量标准，所谓基本操作语句是指算法中重复执行次数和算法的执行时间成正比的语句，它是对算法执行时间贡献最大的语句。对于上面两个矩阵相乘的算法，当n趋向于无穷大时，有
当n充分大时，f（n）与n 3 的比是一个不为零的常数，即f（n）与n 3 是同阶的，两者处于同一数量级（Order of Magnitude）。这里，用“O”表示数量级。可记作T（n）=O（f（n））=O（n 3 ）。由此可得算法时间复杂度定义如下：
算法的时间复杂度（Time Complexity），即算法的时间量度，就是算法中基本操作语句（贡献最大的语句）执行的次数是问题规模n的某个函数f（n），记作：
T（n）=O（f（n））
它表示随问题规模n的增大，算法的执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。实际上，算法的时间复杂度分析是一种时间增长趋势分析。
上述公式的含义是为T（n）找到一个上界，T（n）=O（f（n））是指存在着正常量c和一个足够大的正整数n 0 ，使得n≥n 0 ，有0≤T（n）≤cf（n）。T（n）的上界可能有多个，通常只保留最高阶，忽略其低阶和常系数。例如，f（n）=2n 3 +2n 2 +n，则T（n）=O（n 3 ）。
一般情况下，随n的增大，T（n）的增长较慢的算法为最优的算法。例如，在下列三段程序段中，给出基本操作x=x+1的时间复杂度分析。
一般情况下，一个没有循环或者循环次数与问题规模n无关的算法，记作O（1），称为常量阶。程序段（1）的时间复杂度为O（1）；程序段（2）的时间复杂度为O（n），我们把它称为线性阶；程序段（2）的时间复杂度为O（n 2 ），我们把它称为平方阶。此外算法的时间复杂度还有对数阶O（log 2 n）、指数阶O（2 n ）等。
常用的时间复杂度所耗费的时间从小到大依次是：O（1）<O（log 2 n）<O（n）<O（n 2 ）<O（n 3 ）<O（2 n ）<O（n!）<O（n!）。
算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下，具有指数级的时间的复杂度算法只有当n足够小时才是可使用的算法。具有常量阶、线性阶、对数阶、平方阶和立方阶的时间复杂度算法是常用的算法。一些常用的时间复杂度频率表如表1.2所示。
表1.2 常用的时间复杂度频率表
一些常见函数的增长率如图1.10所示。
图1.10 常见函数的增长率
一般情况下，算法的时间复杂度只需要考虑算法中的基本操作，即算法中最深层循环体内的操作。
【例1.1】 分析以下程序段的时间复杂度。
该程序段中的基本操作是第二层for循环中的语句，即x++和a[i][j]=x，其语句频度为（n-1）（n-2）/2。因此，其时间复杂度为O（n 2 ）。
【例1.2】 分析以下算法的时间复杂度。
该函数fun（）的基本运算是i=i*2，设执行时间为T（n），则2 T（n） ≤n，有T（n）≤log 2 n=O（log 2 n）。因此，时间复杂度为O（log 2 n）。
【例1.3】 分析以下算法的时间复杂度。
该算法中的基本操作是while循环中的语句，设while循环次数为f（n），则变量i为从0到f（n），因此循环次数为f（n）*（f（n）+1）/2≤n，则
，根据时间复杂度定义，T（n）≤cf（n），故时间复杂度为
。
【例1.4】 一个算法所需时间由以下递归方程表示，分析算法的时间复杂度。
因此，该算法的时间复杂度为O（2 n ）。
在有些情况下，算法的基本操作的重复执行次数还依赖于输入的数据集。例如，在以下的冒泡排序算法中：
基本操作是交换相邻数组中的整数部分。当数组a中的初始序列为从小到大有序排列时，基本操作的执行次数为0；当数组中初始序列为从大到小排列时，基本操作的执行次数为n（n-1）/2。对这类算法的分析，一种方法是计算所有情况的平均值，这种计算方法称为平均时间复杂度；另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。上述冒泡排序时的平均时间复杂度和最坏时间复杂度分别为T（n）=O（n 2 ）。一般情况下，在没有特殊说明情况下，指的都是最坏时间复杂度。
算法的空间复杂度通过计算算法所需的存储空间实现。算法空间复杂度的计算公式记作：
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）。