圈复杂度=1+ #if语句？

Question

我找到了以下关于圈复杂度维基百科的段落

可以证明，任何只有一个入口点和一个出口点的结构化程序的圈复杂度等于该程序中包含的决策点的数目(即"if“语句或条件循环)加上一个。

这意味着两个任意嵌套的if语句的圈复杂度为3：

if (a)
{
    if (b)
    {
        foo();
    }
    else
    {
        bar();
    }
}
else
{
    baz();
}

由于这三种功能之一将被调用，我的直觉同意3。

但是，也可以按顺序编写两个任意的if语句，而不是嵌套它们：

if (a)
{
    foo();
}
else
{
    bar();
}

if (b)
{
    baz();
}
else
{
    qux();
}

现在，在代码中有四条路径：

• 福阿湾
• 福，夸克斯
• 巴兹酒吧
• 酒吧，qux

因此，这个片段的圈复杂度不应该是4而不是3吗？

我是否误解了引用的段落？

Answer 1

圈复杂度定义为代码中的线性无关路径的数目。

在您的第二个示例中，我们有以下运行的路径。

| # |   A   |    B  |  Nodes hit   |
| 1 | true  | true  |  foo() baz() |
| 2 | true  | false |  foo() qux() |
| 3 | false | true  |  bar() baz() |
| 4 | false | false |  bar() qux() |

这里的执行路径数是4，这是完全正确的，但圈复杂度是3。

关键在于理解圈复杂度是如何衡量的：

定义：

线性无关路径是通过程序引入至少一个不包含在任何其他线性无关路径中的新边的任何路径。

来自http://www.ironiacorp.com/

第四条路径与前三条路径不线性无关，因为它没有引入任何未包含在前三条路径中的新节点/程序语句。

正如在维基百科文章上提到的，圈复杂度总是小于或等于理论上唯一的控制流路径的数量，并且总是大于或等于实际可实现的执行路径的最小数目。

(要验证第二条语句，想象一下如果b == a在输入您描述的代码块时始终是 true )。

Answer 2

我同意完美主义者的解释。以下是对Java语言的一种更非正式的解释：

McCabe方法的圈复杂度(McCC)表示为该方法中独立控制流路径的个数。它表示源代码中可能的执行路径数的下限，同时也是实现完整分支测试覆盖率所需的最小测试用例数的上限。度量的值计算为下列指令的数量加1: if，for，foreach，while，do-while，case标签(属于开关指令)，catch，条件语句(?:)。此外，逻辑“和”(&&)和“(&&)和逻辑”或“(\)”表达式也会将1添加到值中，因为它们的短路计算可能会根据第一个操作数而导致分支。以下说明不包括在内:否则，开关，默认标签(它属于开关指令)，最后尝试。