程序复杂性度量.doc

程序复杂性度量
　　程序复杂性主要指模块内程序的复杂性。它直接关联到软件开发费用的多少，开发周期的长短和软件内部潜伏错误的多少。同时它也是软件可理解性的另一种度量。

　　减少程序复杂性，可提高软件的简单性和可理解性，并使软件开发费用减少，开发周期缩短，软件内部潜藏错误减少
　　一、代码行度量法
　　度量程序的复杂性，最简单的方法就是统计程序的源代码行数。此方法基于两个前提：

　　（1） 程序复杂性随着程序规模的增加不均衡地增长；

　　（2） 控制程序规模的方法最好是采用分而治之的办法。将一个大程序分解成若干个简单的可理解的程序段。

　　方法的基本考虑是统计一个程序模块的源代码行数目，并以源代码行数做为程序复杂性的度量。若设每行代码的出错率为每 100行源程序中可能有的错误数目， 例如每行代码的出错率为1％，则是指每 100行源程序中可能有一个错误。

　　Thayer曾指出，程序出错率的估算范围是从0.04％～ 7％之间，即每100行源程序中可能存在0.04～7个错误。他还指出，每行代码的出错率与源程序行数之间不存在简单的线性关系。Lipow进一步指出，对于小程序，每行代码的出错率为1.3％～1.8％；对于大程序，每行代码的出错率增加到2.7％～3.2％之间，但这只是考虑了程序的可执行部分，没有包括程序中的说明部分。Lipow及其他研究者得出一个结论：对于少于100个语句的小程序，源代码行数与出错率是线性相关的。随着程序的增大，出错率以非线性方式增长。所以，代码行度量法只是一个简单的，估计得很粗糙的方法。
　　二、McCabe度量法
　　McCabe度量法是一种基于程序控制流的复杂性度量方法。McCabe定义的程序复杂性度量值又称环路复杂度，它基于一个程序模块的程序图中环路的个数。

　　如果把程序流程图中每个处理符号都退化成一个结点，原来联结不同处理符号的流线变成连接不同结点的有向弧，这样得到的有向图就叫做程序图。

　　计算有向图G的环路复杂性的公式：

　　V(G)＝m－n＋2

　　其中，V（G）是有向图G中的环路个数 ，m是图G中有向弧个数 ，n是图G中结点个数。

　　以图9-5-1为例，其中，结点数n＝11，弧数m＝12，则有

　　V（G）＝m－n＋2＝12－11＋2＝3。

　　即McCabe环路复杂度度量值为3 。它也可以看做由程序图中的有向弧所封闭的区域个数。

图 9-5-1　程序图的例子
　　当分支或循环的数目增加时，程序中的环路也随之增加，因此McCabe环路复杂度度量值实际上是为软件测试的难易程度提供了一个定量度量的方法，同时也间接地表示了软件的可靠性。实验表明，源程序中存在的错误数以及为了诊断和纠正这些错误所需的时间与McCabe环路复杂度度量值有明显的关系。
　　Myers建议 ，对于复合判定，例如（A＝0）∩（C＝D）∪（X＝'A'）算做三个判定。
　　利用McCabe环路复杂度度量时，有几点说明。
　　·环路复杂度取决于程序控制结构的复杂度。当程序的分支数目或循环数目增加时其复杂度也增加 。环路复杂度 与程序中覆盖的路径条数有关。

　　·环路复杂度是可加的。例如，模块A的复杂度为3 ，模块B的复杂度为4，则模块A与模块B的复杂度是7。

　　·McCabe建议，对于复杂度超过10的程序，应分成几个小程序，以减少程序中的错误 。Walsh 用实例证实了这个建议的正确性 。他发现，在McCabe复杂度为10的附近，存在出错率的间断跃变。

　　·McCabe环路复杂度隐含的前提是：错误与程序的判定加上例行子程序的调用数目成正比。而加工复杂性、数据结构、录入与打乱输入卡片的错误可以忽略不计。
　　三、Halstead的软件科学
　　Halstead软件科学研究确定计算机软件开发中的一些定量规律，它采用以下一组基本的度量值，这些度量值通常在程序产生之后得出，或者在设计完成之后估算出。

　　1.程序长度，即预测的Halstead长度

　　令n1表示程序中不同运算符（包括保留字）的个数，令n2表示程序中不同运算对象的个数，令H表示“程序长度”，则有

　　H＝n1·log2n1 +n2·log2n2

　　这里，H是程序长度的预测值，它不等于程序中语句个数。在定义中，运算符包括：

　　算术运算符　　赋值符（＝或:＝）　　　　数组操作符
　　逻辑运算符　　分界符（，或；或:）　　子程序调用符
　　关系运算符　　括号运算符　　　　　　 循环操作符等

　　特别地，成对的运算符，例如“ BEGIN…END ”、“ FOR…TO ”、“REPEAT…UNTIL”、“WHILE…DO”、“IF…THEN…ELSE”、“（…）”等都当做单一运算符。

　　运算对象包括变量名和常数。

　　2.实际的Halstead长度

　　设N1为程序中实际出现的运算符总个数，N2为程序中实际出现的运算对象总个数，N为实际的Halstead长度，则有N＝N1+N2

　　3.程序的词汇表

　　Halstead定义程序的词汇表为不同的运算符种类数和不同的运算对象种类数的总和。若令n为程序的词汇表，则有n＝n1+n2

　　图9-5-2是用FORTRAN语言写出的交换排序的例子。

图 9-5-2　一个交换排序程序的例子
　　因此有：预测的词汇量
　　H＝n1·log2n1+n2·log2n2＝10·log210+7·log27 ＝52.87

　　实际的词汇量N＝N1+N2＝28+22＝50

　　程序的词汇表n＝n1+n2＝10+7＝17

　　4.程序量V
　　程序量V，可用下式算得

　　V＝(N1+N2)·log2(n1+n2)

　　它表明了程序在“词汇上的复杂性”。其最小值为

　　V*＝(2+n2*)·log2(2+n2*)

　　这里，2表明程序中至少有两个运算符：赋值符“:＝”和函数调用符“f()”，n2*表示输入／输出变量个数。对于图9-5-2的例子，利用n1，N1，n2，N2，可以计算得：

　　V＝(28+22)·log2(10+7)＝204

　　等效的汇编语言程序的 V＝328。这说明汇编语言比FORTRAN语言需要更多的信息量（以bit表示）。

　　5.程序量比率（语言的抽象级别）

　　L＝V*∕V或L＝(2∕n1)·(n2∕N2)

　　这里，N2＝n2·log2n2。它表明了一个程序的最紧凑形式的程序量与实际程序量之比，反映了程序的效率。其倒数：

　　D＝1∕L

　　表明了实现算法的困难程度。有时，用L表达语言的抽象级别，即用L衡量在表达程序过程时的抽象程度。对于高级语言 ，它接近于1，对于低级语言，它在0～1之间。下面列出的是根据经验得出的一些常用语言的语言抽象级别。
语言
L的平均值
English Prose（英语散文）
PL/1
ALGOL68
FORTRAN
Assembler（汇编语言）
2.16
1.53
2.12
1.14
0.88
　　6.程序员工作量

　　E＝V∕L

　　7.程序的潜在错误

　　Halstead度量可以用来预测程序中的错误。认为程序中可能存在的差错应与程序的容量成正比。因而预测公式为

　　B＝(N1+N2)·log2(n1+n2)∕3000＝V∕3000

　　B表示该程序的错误数。例如 ，一个程序对75个数据库项共访问1300次，对150个运算符共使用了1200次，那么预测该程序的错误数：

　　B＝(1300+1200)·log2(75+150)∕3000＝6.5

　　即预测该程序中可能包含6～7个错误。

　　Halstead的重要结论之一是：程序的实际 Halstead长度N可以由词汇表n算出 。即使程序还未编制完成，也能预先算出程序的实际Halstead长度N， 虽然它没有明确指出程序中到底有多少个语句。

　　这个结论非常有用。经过多次验证，预测的 Halstead 长度与实际的Halstead长度是非常接近的。

　　Halstead度量是目前最好的度量方法。但它也有缺点：

　　·没有区别自己编的程序 与别人编的程序 。这是与实际经验相违背的。这时应将外部调用乘上一个大于 1的的常数Kf（应在1～5之间，它与文档资料的清晰度有关）。

　　·没有考虑非执行语句。补救办法：在统计n1、n2、N1、N2时，可以把非执行语句中出现的运算对象，运算符统计在内。

　　·在允许混合运算的语言中，每种运算符必须与它的运算对象相关。如果一种语言有整型、实型、双精度型三种不同类型的运算对象，则任何一种基本算术运算符（＋、－、×、／）实际上代表了 4种运算符。如果语言中有 4种不同类型的算术运算对象，那么每一种基本算术运算符实际上代表了种运算符。在计算时应考虑这种因数据类型而引起差异的情况。

　　·没有注意调用的深度。Halstead公式应当对调用子程序的不同深度区别对待。在计算嵌套调用的运算符和运算对象时，应乘上一个调用深度因子。这样可以增大嵌套调用时的错误预测率。

　　·没有把不同类型的运算对象 ，运算符与不同的错误 发生率联系起来，而是把它们同等看待。例如，对简单IF语句与WHILE语句就没有区别。实际上，WHILE语句复杂得多，错误发生率也相应地高一些。

　　·忽视了嵌套结构（嵌套的循环语句、嵌套IF语句、括号结构等）。一般地，运算符的嵌套序列，总比具有相同数量的运算符和运算对象的非嵌套序列要复杂得多。解决的办法是对嵌套结果乘上一个嵌套因子。