以下程序的控制流图和圈复杂度

Question

insertion_procedure (int a[], int p [], int N)
{
    int i,j,k;
    for (i=0; i<=N; i++) p[i] = i;
    for (i=2; i<=N; i++)
    {
        k = p[i];
        j = 1;
        while (a[p[j-1]] > a[k]) {p[j] = p[j-1]; j--}
        p[j] = k;
    }
}

我需要计算这段代码的圈复杂度，然后提出一些白盒测试用例和黑盒测试用例。但是我在为这段代码制作控制流程图时遇到了困难。

同时感谢任何关于测试用例的帮助。

- AJ.

---

这是什么语言？它看起来像C语言，除了声明中的“Int”而不是“int”。如果它是C语言，那么没有嵌套的for循环，而是一个while循环嵌套在for循环中。 - David Thornley

哦，是的，没有嵌套的for循环。这是C语言。 - AJ.

Answer 1

首先对语句进行编号:

 insertion_procedure (int a[], int p [], int N)
 {
(1)    Int i,j,k;
(2)    for ((2a)i=0; (2b)i<=N; (2c)i++) 
(3)        p[i] = i;
(4)    for ((4a)i=2; (4b)i<=N; (4c)i++)
       {
(5)       k=p[i];j=1;
(6)       while (a[p[j-1]] > a[k]) {
(7)           p[j] = p[j-1]; 
(8)           j--
          }
(9)          p[j] = k;
       }

现在，您可以清楚地看到哪些语句首先执行，哪些最后执行等等，因此绘制cfg变得简单。

现在，计算圈复杂度有三种方法：

1. 计算图形上的区域数量：4
2. 谓词数量（图上的红色）+ 1：3 + 1 = 4
3. 边数减去节点数加2：14-12 + 2 = 4。

- Vincent Ramdhanie

---

出于好奇，你是用什么工具生成流程图的？ - James McNellis

@James McNellis 我使用MS Visio绘制了CFG。 - Vincent Ramdhanie

@VincentRamdhanie 很好的解释。但是我有一个疑问：控制从4b是否可能直接跳转到函数的结尾？（类似于从2b跳转到4a）？这样做没有被考虑的具体原因吗？我在这里错过了什么？ - Jay

其实 @Jay 你可能是对的。4B 是一个谓词，因此应该有两个箭头离开。奇怪为什么之前没有人注意到这一点。 - Vincent Ramdhanie

好的，我明白了。它将从4b到10，但不会从9到10。因此，总区域数量将保持不变。 - Jay

Answer 2

圈复杂度为4。

过程的复杂度为1，for循环的复杂度为1，while循环的复杂度为1，while循环中的if条件的复杂度为1。

- Darin Dimitrov

---

是的，但它们处于相同的嵌套级别，因此代码中只有一条路径，没有if语句。 - Darin Dimitrov

@AJ。我完全同意你的观点。我刚刚在原始答案中添加了类似的评论。否则，如果您知道解释，可以在此处添加以使所有人受益。 - Jay

2个for循环 + 1个while循环 + 1个过程 = 4。需要帮助，能否确认这个维基链接的真实性。我认为这里的复杂度应该是4。但是它被提到了3。我需要有人来证明一下。https://en.wikipedia.org/wiki/Cyclomatic_complexity#/media/File:Control_flow_graph_of_function_with_loop_and_an_if_statement.svg - Avan

Answer 3

您还可以使用麦凯布公式M = E-N + 2C来评估代码的复杂度。
其中E表示边数，N表示节点数，C表示连通组件数量，M表示圈复杂度。

E = 14
N = 12
C = 1

M = 14-12 + 2*1 = 4

- Lineker