5．1．3　程序复杂性度量

经过详细设计后每个模块的内容都非常具体了，因此可以使用软件设计的基本原理和概念仔细衡量它们的质量。但是，这种衡量毕竟只能是定性的，人们希望能进一步定量度量软件的性质。定量度量程序复杂程度的方法很有价值，把程序的复杂度乘以适当的常数即可估算出软件中故障的数量及软件开发时的工作量。定量度量的结构可以用于比较两个不同设计或两种不同算法的优劣；程序的定量的复杂程度可以作为模块规模的精确限度。

目前，比较成熟的软件复杂程度定量度量方法主要有McCabe方法和Halstead方法两种。

1．McCabe方法

首先需要画出程序图，所谓的程序图可以看成“退化了的”程序流程图，也就是把程序流程图中每个处理符号都退化成一个点，原来连接不同处理符号的箭头变成连接这些点的有向弧，这样得到的有向图就成为程序图。程序图仅仅描绘程序内部的控制流程，完全不表现对数据的具体操作及分支或循环的具体条件。通常程序图中开始点后的那个节点称为入口点，称停止点前面的那个节点称为出口点。

用McCabe方法度量得出的结果称为程序的环形复杂度，它等于强连通的程序图中线性无关的有向环的个数。环形复杂度的计算方法如下。

根据图论，在一个强连通的有向图中线性无关环的个数由下面的公式给出：

V（G）＝m－n＋p

式中：V（G）是有向图G中的环数；

m是有向图G中的弧数；

n是有向图G中的节点数；

p是有向图G中分离部分的数目。

对于一个正常的程序来说，应该能够从程序图内的入口点到达图中任何一个节点（一个不能到达的节点代表永远不能执行的程序代码，显然是错误的），因此，程序图总是连通的，也就是说，p＝1。

所谓强连通图是指从图中一个节点出发都可以到达所有其他节点。程序图通常不是强连通的，因为从图中较低的（较靠近出口的）节点往往不能到达较高的节点。然而，如果从出口点到入口点画一条虚线弧，则程序图必然成为强连通的。这个结论有下列三点理由：

（1）从入口点总能到达图中任何一点，否则程序有错；

（2）从图中任何一点总能到达出口点，否则程序有错；

（3）经过从出口点到入口点的弧，可以从出口点达到入口点。

计算环形复杂度还有其他方法，例如，对于平面图而言，环形复杂度等于强连通的程序图在平面上围成的区域个数。程序的环形复杂度取决于程序流程控制的复杂程度，亦即取决于程序结构的复杂程度。当程序内部分支数或循环个数增加时，环形复杂度也随之增加，因此它是对测试难度的一种定量度量，也能对软件最终的可靠性给出某种预测。

研究大量程序后发现，环形复杂程度高的程序往往是最困难、最容易出问题的程序。实践表明，模块规模以V（G）≤10最佳，也就是说，V（G）＝10是模块规模的一个更科学、更精确的上限。

2．Halstead方法

Halstead方法是另一个著名的方法，根据程序中运算符和操作数的总量来度量程序的复杂程度。

令N₁为程序中运算符出现的总次数，N₂为操作数的总次数，程序长度N定义为

N＝N₁＋N₂

在完成详细设计之后，可以知道程序中使用的不同运算符（包括关键字）的个数n₁，以及不同操作数（变量和常数）的个数n₂。Halstead方法给出了预测程序长度的公式，即

H＝n1log2n1＋n2log2n2

多次验证都表明，预测的长度H与实际长度N非常接近。

Halstead方法还给出了预测程序中包含错误的个数的公式，即

E＝Nlog₂（n₁＋n₂）／3000

有人曾对从300条到12000条语句范围内的程序核实上述公式，发现预测的错误数与实际错误数相比，其误差在8%以内。