圈复杂度= 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();
}

现在代码中有四条路径:

• foo,baz
• foo,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/

第4条路径与前三条路径不是线性独立的,因为它没有引入任何未包含在前三条路径中的新节点/程序语句.

如维基百科文章所述,圈复杂度总是小于或等于理论唯一控制流路径的数量,并且总是大于或等于实际可实现的执行路径的最小数量.

(为了验证第二个语句,想象一下当输入你描述的代码块时b == a 总是如此).