软件设计－程序复杂程度的定量度量
上一篇 /
下一篇 2008-02-20 17:38:16
/ 个人分类：小知识
程序复杂性主要指模块内程序的复杂性。它直接关联到软件开发费用的多少，开发周期的长短和软件内部潜伏错误的多少。
意义：
程序的复杂程度乘以适当常数即可估算出软件中故障的数量以及软件开发需要的工作量。
可以比较两个不同的设计和算法的优劣。
定量的复杂程度可作为模块规模的精确限度。
复杂性度量需要满足的假设
为了度量程序复杂性，要求：
它可以用来计算任何一个程序的复杂性；
对于不合理的程序，例如对于长度动态增长的程序，或者对于原则上无法排错的程序，不应当使用它进行复杂性计算；
如果程序中指令条数、附加存储量、计算时间增多，不会减少程序的复杂性。
代码行度量法
度量程序的复杂性，最简单的方法就是统计程序的源代码行数。此方法的基本考虑是统计一个程序的源代码行数，并以源代码行数作为程序复杂性的度量
源代码行数度量法基于两个前提：
程序复杂性随着程序规模的增加不均衡地增长；
控制程序规模的方法最好是采用分而治之的办法。将一个大程序分解成若干个简单的可理解的程序段。
McCabe方法
McCabe(麦坎比)度量法，又称环路复杂性度量，是一种基于程序控制流的复杂性度量方法。
它基于一个程序模块的程序图中环路的个数，因此计算它先要画出程序图。程序图是退化的程序流程图。流程图中每个处理都退化成一个结点，流线变成连接不同结点的有向弧。
把程序流程图中每个处理符号都退化成一个点，连接不同处理符号的箭头变成连接不同点的有向弧，这样得到的有向图就称为流程图
程序的环形复杂度等于强连通的流图中线性无关的有向环的个数。
程序图仅描述程序内部的控制流程，完全不表现对数据的具体操作，以及分支和循环的具体条件。
计算环路复杂性的方法：根据图论，在一个强连通的有向图G中，环的个数由以下公式给出：
V(G)＝m－n＋p
其中，V(G)是有向图G中环路个数，m是图G中弧数，n是图G中结点数，p是图G中的强连通分量个数。
在一个程序中，从程序图的入口点总能到达图中任何一个结点，因此，程序总是连通的，但不是强连通的。为了使图成为强连通图，从图的入口点到出口点加一条虚线表示的有向边，使图成为强连通图。这样就可以使用上式计算环路复杂性了。
以上图为倒，其中结点数n=11，弧数m=13，p=1。则有：V(G)=m-n+p=13-11+1=3。
几点说明
环路复杂度取决于程序控制结构的复杂度。当程序的分支数目或循环数目增加时其复杂度也增加。环路复杂度与程序中覆盖的路径条数有关。
环路复杂度是可加的。例如，模块A的复杂度为3，模块B的复杂度为4，则模块A与模块B的复杂度是7。
这种度量的缺点是：
对于不同种类的控制流的复杂性不能区分
简单IF语句与循环语句的复杂性同等看待
嵌套IF语句与简单CASE语句的复杂性是一样的
模块间接口当成一个简单分支一样处理
一个具有1000行的顺序程序与一行语句的复杂性相同
Halstead方法
根据程序中运算符和操作数的总数来度量程序的复杂度.程序
长度N定义为:
N=N1+N2
其中:N1表示运算符总数,N2表示操作数总数
若已知程序中程序中使用的不同运算符个数n1和不同操作数的
个数n2 ,则预测程序长度的公式为:H=n1log2 n1+n2log2 n2
预测程序中错误个数的公式为:
E=N log2( n1+n2)/3000
例如，一个程序对75个数据库项共访问1300次，对150个运算符共
使用1200次，那么预测该程序的错误数：
B＝(1300+1200)*log2(75+150)/3000=6.5。即预测该程序中可能包
含6-7个错误。
Halstead的重要结论
程序的实际Halstead长度N可以由词汇表n算出。即使程序还未编制完成，也能预先算出程序的实际Halstead长度N，虽然它没有明确指出程序中到底有多少个语句。
这个结论非常有用。经过多次验证，预测的Halstead长度与实际的Halstead长度是非常接近的。
收藏
举报
TAG:
小知识
