IF（（A＞ B）AND（C＞ D））和IF（（A＞ B）OR（C＞ D））的圈复杂度 [英] Cyclomatic complexity of IF((A>B) AND (C>D)) and IF((A>B) OR (C>D))

问题描述

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

  IF（（A&B; B）AND（C> ; D））
 {a = a + b; c = c + d;} 
  

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

另一个代码

  IF（（A> B）OR（C&D; D））
 {a = a + b; c = c + d;} 
  

上面代码的复杂度是= 4 + 1 = 5，

是否以上复杂性是否正确？

解决方案

这两种复杂性相同且相等3，以4种方式计算。我同意尼尔使用De Morgan证明它们是相同的，我认为可以从对复杂度计数至关重要的图形中看出相同的含义。

Graphics

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

解释词：

1. McCabe图由基本块组成，这意味着只要控制以线性方式在它们之间传递，我就可以将许多语句折叠为一个。


2. 我将您的代码视为简单过程，一个入口点，一个出口点


3. 出口点被添加为汇点，汇点在此结束。在这里注意到，因为我很少有示例可以从代码中为McCabe计算生成图形，而我也没有做过，但是考虑到基本块和节点/边的含义，我认为这很自然。


4. 出口和入口点之间的边缘仅与简化复杂度计算相关，因此注释和不同的标记（颜色，箭头）。


5. 基本块由可能通过的指令分隔


6. 引用McCabe本人，AND和OR将+1加到复杂度上，因为它们基本上是 if and if 和 if或if ，所以两个if。因此，我的第二个节点是一个单独的节点。

如您所见，两个代码段之间的数字没有区别。节点，边缘，区域都相同。区别在于哪个节点与哪个节点连接，这来自短路的工作方式。显然，对于没有语言的语言，图形必须有所不同。

复杂性定义

有不止一个。复杂度等于

Edges-节点+ 2 *（出口）

Edges = 5;节点= 4; exits = 1;

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

边-节点和出口提供了强连接图

边= 6;节点= 4; exits = 1;

复杂度= 6-4 + 1 = 3。这个定义是因为它在拓扑上更有意义，并且在循环计数（图形方式）方面更容易想到。当您考虑为许多例程/函数（如类中的所有方法）计算复杂度时，它会更加有用。认为可以在循环中调用该函数就很有意义。但是我离题了。

地区

地区：3。

这来自于欧拉公式，即
区域+节点-边缘= 2
重新命名为：
区域=边缘-节点+ 2

因此区域的数量与复杂度相同（假设有一个出口点）。这是为了简化从图的计数（在一次退出子例程中）。

决策点+ 1

McCabe本人指出

实际上，复合谓词（例如IF c1和c2）被视为贡献
两个到复杂度，因为如果没有连接词AND我们将拥有IF c1 THEN IF c2 THEN
，它具有两个谓词。因此，出于测试目的，已经发现
在计算复杂度时更方便地计算条件而不是谓词

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

复杂度= 2 + 1 = 3。

值得注意的是，圈复杂度从计数周期开始，但在实际操作中以条件计数结束。

进一步阅读

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

Wikipedia有一篇很好的文章依赖这篇文章，尽管我发现如果不遵循基本块和连接的组件，这是不够的：

1. http：// en.wikipedia.org/wiki/Cyclomatic_complexity


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


3. http：// zh-CN。 wikipedia.org/wiki/Connected_component_(graph_theory）

我在钱伯斯的页面上找到了一个简洁但很好的摘要： a href = http://www.chambers.com.au/glossary/mc_cabe_cyclomatic_complexity.php rel = noreferrer> 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&a mp; hl = pl& pg = PR1＃v =一页

I want to know the cyclomatic complexity of two section of code,

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

as far my knowledge the cyclomatic complexity of above code=2+1=3,

Another code

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

Complexity of the above code is=4+1=5,

whether the above complexities are correct or not?

解决方案

Both complexities are same and equal 3, counted in 4 ways. I agree with Neil on using De Morgan proving that they are same, I think same can be seen from graphs where it matters for complexity counting.

Graphs

Let's start with graphs for both code pieces.

Word of explanation:

1. McCabe graph consists of basic blocks, meaning that I can collapse many statements into one, as long as control passes between them linearly.
2. I treated your code as simple procedure, one entry point, one exit point.
3. Exit point is added as a sink where it all ends. Noting here as I have few examples that build graphs from code for McCabe computations and none I recall does that, but I think this feels natural, given what are basic blocks and what nodes / edges are to mean.
4. Edge between exit and entry point is only relevant for simplifying complexity computing, thus the note and different marking (color, arrow).
5. Basic blocks are delimited by instructions that may pass control non-linearly: while, for, if, etc.
6. Citing McCabe himself, AND and OR add +1 to complexity, since they basically are if and if and if or if, so two ifs. Thus my second node being a separate node.

As you can see, between both code pieces there's no difference in numbers. Nodes, edges, regions all are the same. The difference is which node connects with which node, and this comes from how short-circuiting works. Obviously for languages without it, graphs need to be different.

Complexity definitions

There is more than one. Complexity equals

Edges - Nodes + 2*(exits)

Edges = 5; Nodes = 4; exits = 1;

Complexity = 5-4+2*(1) = 3 in both cases. This definition doesn't need a strongly connected graph so we drop the added edge.

Edges - Nodes + exits provided strongly connected graph

Edges = 6; Nodes = 4; exits = 1;

Complexity = 6-4+1 = 3 in both cases. This definition came to be for it makes more sense topologically and is simpler to think of in terms of cycle counting (graph-wise). It is more useful when you think of counting complexity for many routines / functions, like all methods in a class. It makes then sense to think that function may be called in a loop. But I digress.

Regions

Regions: 3.

This comes from Eulerian formula that Regions + Nodes - Edges = 2 Rewording this: Regions = Edges - Nodes + 2

So number of regions is same as complexity (assuming one exit point). This was meant to simplify counting complexity from graph, in one-exit sub-routine.

Decision points + 1

McCabe himself noted that

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

In both code pieces we have one compound conditional, so Decisions = 2;

Complexity = 2+1 = 3.

It's worth noting that cyclomatic complexity started as counting cycles, but ended as counting conditionals for practical purposes.

Further reading

First try McCabe's paper itself: http://www.literateprogramming.com/mccabe.pdf

Wikipedia has a good article relying on the paper, though I found it insufficient without following BASIC BLOCKS and 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)

I found a concise yet good summary at Chambers' page: http://www.chambers.com.au/glossary/mc_cabe_cyclomatic_complexity.php

The book "Integrated Approach to Software Engineering" in chapter 8 has an example illustrating complexity calculation (though I think they ate one edge on a graph, figure 8.7).

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

这篇关于IF（（A＞ B）AND（C＞ D））和IF（（A＞ B）OR（C＞ D））的圈复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！