IF的循环复杂度((A> B)和(C> D))和IF((A> B)OR(C> D))

Question

我想知道两段代码的圈复杂度,

IF((A>B) AND (C>D)) 
{ a=a+b;c=c+d;}

据我所知,上述代码的圈复杂度= 2 + 1 = 3,

另一个代码

IF((A>B) OR (C>D))
{a=a+b;c=c+d;}

上面代码的复杂性是= 4 + 1 = 5,

上述复杂性是否正确？

Answer 1

两种复杂性相同且相等3,以4种方式计算.我同意Neil使用De Morgan证明它们是相同的,我认为同样可以从图中看出复杂计数的重要性.

图表

让我们从两个代码片段的图表开始.

如果+或

如果+和

解释的话:

McCabe图由基本块组成,这意味着只要控制在它们之间线性传递,我就可以将许多语句合并为一个.
我将您的代码视为简单的过程,一个入口点,一个出口点.
退出点被添加为接收器,它将全部结束.注意到这里我没有几个例子可以从McCabe计算的代码构建图表,但我没有回忆过这一点,但我认为这看起来很自然,因为基本块是什么,节点/边是什么意思.
出口和入口点之间的边缘仅与简化复杂度计算相关,因此笔记和不同的标记(颜色,箭头)相关.
基本块由可以非线性地传递控制的指令分隔:while,for,if等.
援引麦凯布自己,AND和OR添加+1复杂性,因为他们基本上是if and if和if or if,于是两个IFS.因此我的第二个节点是一个单独的节点.

如您所见,两个代码片段之间的数字没有区别.节点,边缘,区域都是相同的.不同之处在于哪个节点与哪个节点连接,这来自于短路的工作原理.显然,对于没有它的语言,图形需要不同.

不止一个.复杂性等于

边缘= 5; 节点= 4; 退出= 1;

两种情况下复杂度= 5-4 + 2*(1)= 3.此定义不需要强连接图,因此我们删除了添加的边.

边缘= 6; 节点= 4; 退出= 1;

两种情况下复杂度= 6-4 + 1 = 3.这个定义是因为它在拓扑上更有意义,并且在循环计数(图形方面)方面更容易思考.当您考虑计算许多例程/函数的复杂性(如类中的所有方法)时,它会更有用.认为可以在循环中调用函数是有意义的.但我离题了.

地区:3.

这来自欧洲公式,区域+节点 - 边缘= 2重写:区域=边缘 - 节点+ 2

因此,区域的数量与复杂性相同(假设一个出口点).这意味着在一次退出子程序中简化图表的计算复杂性.

麦凯布自己也注意到了这一点

在实践中,复合谓词如IF"c1 AND c2"THEN被视为对复杂性有贡献,因为没有连接词,我们将得到IF c1那么如果c2那么它有两个谓词.出于这个原因并且出于测试目的,已经发现在计算复杂度时计算条件而不是谓词更方便

在两个代码段中,我们有一个复合条件,因此Decisions = 2;

复杂度= 2 + 1 = 3.

值得注意的是,圈复杂度始于计数周期,但最终是为了实际目的而计算条件.

维基百科有一篇很好的文章依赖于论文,但我发现它没有遵循BASIC BLOCKS和CONNECTED COMPONENTS:

第8章中的"软件工程集成方法"一书中有一个说明复杂度计算的例子(尽管我认为它们在图形上吃了一条边,图8.7).

Answer 2

我认为它们的圈复杂度相同，均为 3；这可以用德摩根定律来证明。

IF((A>B) OR (C>D)) {a=a+b;c=c+d;} ELSE {}

IF(!((A>B) OR (C>D))) {} ELSE {a=a+b;c=c+d;}

IF(!(A>B) AND !(C>D)) {} ELSE {a=a+b;c=c+d;}

另一种看待它的方法是获取图形并交换条件块和退出点（并反转它们之间的边），这会将其从 AND 转换为 OR，而不改变节点或边的数量。