cyclomatic-complexity - IF((A>B) AND (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 等。

引用 McCabe 本人的话，AND 和 OR 会为复杂性增加 +1，因为它们基本上是 if and if和 if or if ，所以两个如果。因此我的第二个节点是一个单独的节点。

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

复杂性定义

不止一种。复杂性等于

边 - 节点 + 2*(退出)

边 = 5;节点数 = 4；退出 = 1;

在这两种情况下，复杂度 = 5-4+2*(1) = 3。这个定义不需要强连通图，所以我们删除了添加的边。

Edges - 节点 + 导出提供强连接图

边 = 6;节点数 = 4；退出 = 1;

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

地区

区域:3。

这来自欧拉公式
区域 + 节点 - 边 = 2
改写这个:
区域 = 边 - 节点 + 2

因此区域的数量与复杂性相同(假设有一个导出点)。这是为了在单导出子程序中简化图形的计数复杂性。

决策点 + 1

麦凯布本人指出

in practice compound predicates such as IF "c1 AND c2" THEN are treated as contributing two to complexity since without the connective AND we would have IF c1 THEN IF c2 THEN which has two predicates. For this reason and for testing purposes it has been found to be more convenient to count conditions instead of predicates when calculating complexity

在两段代码中，我们都有一个复合条件，所以 Decisions = 2;

复杂度 = 2+1 = 3。

值得注意的是，圈复杂度从计数循环开始，但为了实际目的以计数条件结束。

进一步阅读

先试试McCabe的论文本身: http://www.literateprogramming.com/mccabe.pdf

维基百科有一篇很好的文章依赖于该论文，尽管我发现没有遵循 BASIC BLOCKS 和 CONNECTED COMPONENTS 是不够的:

http://en.wikipedia.org/wiki/Cyclomatic_complexity

http://en.wikipedia.org/wiki/Basic_block

http://en.wikipedia.org/wiki/Connected_component_(graph_theory)

我在钱伯斯的页面上找到了一个简洁但很好的总结: http://www.chambers.com.au/glossary/mc_cabe_cyclomatic_complexity.php

第 8 章中的“Integrated Approach to Software Engineering”一书有一个说明复杂度计算的例子(尽管我认为他们吃掉了图上的一条边，图 8.7)。

http://books.google.pl/books?id=M-mhFtxaaskC&lpg=PA385&ots=jB8P0avJU7&d&hl=pl&pg=PR1#v=onepage