6

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

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，

上述复杂性是否正确？

4

2 回答 2

11

两种复杂度都相同且等于 3，以 4 种方式计算。我同意 Neil 使用 De Morgan 证明它们是相同的，我认为从对复杂性计数很重要的图表中可以看出相同。

图表

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

如果 + 或

如果 + 和

解释词：

  1. McCabe 图由基本块组成，这意味着我可以将许多语句合并为一个，只要控制在它们之间线性传递。
  2. 我将您的代码视为简单的过程，一个入口点，一个出口点。
  3. 出口点被添加为所有结束的接收器。请注意，因为我很少有从 McCabe 计算的代码构建图形的示例，但我记得没有一个示例是这样做的，但我认为这感觉很自然，考虑到什么是基本块以及节点/边的含义。
  4. 出口和入口点之间的边缘仅与简化复杂度计算有关，因此注释和不同的标记（颜色，箭头）。
  5. 基本块由可以非线性传递控制的指令分隔：while、for、if 等。
  6. 引用 McCabe 本人的话，AND 和 OR 会增加复杂性 +1，因为它们基本上是if and ifand if or if，所以有两个 if。因此我的第二个节点是一个单独的节点。

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

复杂性定义

不止一个。复杂度等于

边 - 节点 + 2*（退出）

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

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

边 - 节点 + 出口提供强连通图

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

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

地区

地区：3。

这来自欧拉公式，即 Regions + Nodes - Edges = 2 重新措辞：Regions = Edges - Nodes + 2

所以区域的数量与复杂性相同（假设一个出口点）。这是为了在单出口子例程中简化图表中的计数复杂性。

决策点 + 1

麦凯布本人指出

在实践中，复合谓词如 IF "c1 AND c2" THEN 被视为对复杂性有两个贡献，因为没有连接词 AND 我们将拥有 IF c1 THEN IF c2 THEN，它有两个谓词。由于这个原因和测试目的，在计算复杂度时，计算条件而不是谓词更方便

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

复杂度 = 2+1 = 3。

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

进一步阅读

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

Wikipedia 有一篇很好的文章依赖于该论文，尽管我发现如果不遵循 BASIC BLOCKS 和 CONNECTED COMPONENTS 是不够的：

  1. http://en.wikipedia.org/wiki/Cyclomatic_complexity
  2. http://en.wikipedia.org/wiki/Basic_block
  3. http://en.wikipedia.org/wiki/Connected_component_(graph_theory)

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

第 8 章中的“软件工程集成方法”一书有一个示例说明复杂性计算（尽管我认为他们在图上吃了一条边，图 8.7）。

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

于 2014-02-09T11:03:25.087 回答
3

我认为它们具有相同的圈复杂度 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 而不会更改节点或边的数量。

于 2012-09-26T11:10:28.090 回答