如何计算圈复杂度?

圈复杂度(Cyclomatic complexity)是一种代码复杂度的衡量标准,在1976年由Thomas J. McCabe, Sr. 提出。在软件测试规范中,通常要求每个软件单元的圈复杂度不大于10。

那么,如何计算圈复杂度呢?

要计算圈复杂度,首先要会使用流图。

所谓流图,就是一种表示程序控制流的图形(也称为程序图)。

流图中有3个概念:节点、边、区域。流图中的圆称为节点,一个节点代表一条或多条语句;流图中的箭头线称为边,代表控制流;由边和节点围成的部分称为区域。

流图用于表示程序的控制流,所以程序流程图可以很方便地转换成流图。

实际上,用任何方法表示的过程设计结果都可以转换成流图。

一个程序流程图转换成流图的例子如下:

如何计算圈复杂度?

其中,2、3和4、5节点都是对应程序流程图中的两个语句,但它们都是在同一条路径上,所以在流图中只能是一个节点。

有了流图,就可以开始计算圈复杂度。计算圈复杂度有3种方法,分别和这3个概念相关。

方法1:圈复杂度V(G) = E−N+2,其中E是流图中边的条数,N是流图中节点数。

方法2:圈复杂度V(G) = P+1,其中P是流图中判定节点的数目。在流图中当一个节点分出两条或多条边指向其他节点时,这个节点就是一个判定节点。

方法3:圈复杂度V(G) = R,其中R是区域数。计算区域数时不仅包括由边和节点围起来的区域,也包括图外部未被围起来的那个区域(或者说一个流图的区域数=由边和节点围成的区域数+1)。

对下面这个流图进行圈复杂度如下:

如何计算圈复杂度?

在这个图中,边数E=17,节点数N=13,使用方法1:

圈复杂度=E-N+2=17-13+2=6

这个流图中的判断节点是2、3、5、6、10,所以判断节点数P=5,使用方法2:

圈复杂度=P+1=5+1=6

这个流图中的被围的区域有2、3、10区域,10、11、12、13区域,5、6、8区域,6、7、8区域以及2、3、4、5、6、8、9区域,共5个,所以区域数R=5+1=6,使用方法3:

圈复杂度=6

这正是:

学会计算复杂度,首先学会用流图

会数区域节点边,这个计算不算难

参考书目:软件工程(第4版),作者:张海藩 吕云翔,出版社:人民邮电出版社有限公司

作者简介:王小双,长期从事GJB5000推广、实施、评价、改进的工作,创建《软件工程之思》微信公众号,一直在《软件工程之思》分享GJB5000、CMMI、软件工程的知识和感悟。现致力于GJB5000咨询以及软件过程改进、软件工程能力提升的研究工作。

如何计算圈复杂度?》来自互联网,仅为收藏学习,如侵权请联系删除。本文URL:http://www.hashtobe.com/169.html