1.4 算法复杂度

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面来衡量，即用空间复杂度和时间复杂度来衡量程序的效率。

1.4.1 空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记作S（n）=O（f（n））。

一个算法在计算机存储器上所占用的存储空间，包括算法的输入、输出数据所占用的存储空间、算法本身所占用的存储空间和算法在运行过程中临时占用的存储空间。

● 算法的输入、输出数据所占用的存储空间由要解决的问题决定，是通过参数表由调用函数传递而来的，它不随算法的不同而改变。

● 算法本身所占用的存储空间与算法编写的长短成正比，要压缩这方面的存储空间，就必须编写较短的算法。

● 算法在运行过程中临时占用的存储空间随算法的不同而异。

一个算法所占用的存储空间要从各方面综合考虑。递归算法一般都比较简短，算法本身所占用的存储空间较小，但运行时需要一个附加堆栈，会占用较多的临时存储空间。非递归算法一般较长，因此存储算法本身的空间较大，但运行时需要的存储空间较小。

1.4.2 时间复杂度

计算机科学中，算法的时间复杂度是一个函数，通常用O符号表述，用于定量描述该算法的运行时间。算法中模块n基本操作的重复执行次数计为函数f（n），算法的时间复杂度为T（n）=O（f（n））。

一个算法运行的总时间取决于以下两个方面。

● 每条语句执行一次所需的时间。

● 每条语句的执行次数。

每条语句的执行时间为该语句的执行次数乘以该语句执行一次所需时间。

常见的时间复杂度有：常数阶O（1）、对数阶O（logn）、线性阶O（n）、线性对数阶O（nlogn）、平方阶O（n2 ）、立方阶O（n3 ）等，如表1.2所示。

1.4.3 提高算法效率的方法

下面介绍提高算法效率的几种方法。

1.降低程序复杂度

程序复杂度主要是指模块内部程序的复杂度，往往采用McCabe度量法，用于计算程序模块中环路的个数。实践表明，当程序内分支数或循环个数增加时，环形复杂度也随之增加，模块的环形复杂度以V（G）≤10为宜，也就是说，V（G）=10是环形复杂度的上限。

环形复杂度V（G）主要有如下3种方法。

● 将环形复杂度定义为控制流图中的区域数。

● V（G）=E-N+2，E是控制流图中边的数量，N是控制流图中节点的数量。

● V（G）=P+1，P是控制流图G中判定节点的数量。

【例1-3】计算图1.6的环形复杂度。

【解析】

1)V(G)=6.

分析：图中的区域数为6。

2)V(G)=E-N+2=16-12+2=6.

分析：其中E为控制流图中的边数，N为节点数。

3)V(G)=P+1=5+1=6.

分析：其中P为谓词节点的个数。在控制流图中，节点2、3、5、6、9是谓词节点。

2.选用高效率算法

对算法的空间复杂度和时间复杂度进行优化，从而选择高效的算法。

【例1-4】鸡兔同笼问题：鸡兔共有30只，脚共有90只，问鸡、兔各有多少只？

【解析】设鸡为x只，兔为y只，根据题目要求，列出方程组为：

采用“试凑法”解决方程组的求解问题，将x和y变量的每一个值都带入方程中进行尝试。

方法1：利用二重循环来实现。

【程序运行结果】

时间复杂度：

T(n)=O(n*n)=O(n2 )

方法2：利用一重循环来实现。

时间复杂度：

T(n)=O(n)

方法3：假设鸡兔共有a只，脚共有b只，a为30，b为90。那么方程组为：

时间复杂度：

T(n)=O(1)