-1 
i = 0; 
n=4; //N-Number of nodes present in the graph 
while (i<n-1) do 
j = i + 1;
while (j<n) do 
if A[i]<A[j] then 
swap(A[i], A[j]); 
end do;
i=i+1;
end do;

我必须找到这段代码的圈复杂度，然后建议一些白盒测试用例和黑盒测试用例。但是我在为代码制作 CFG 时遇到了麻烦。

4

1 回答 1

1

浏览复杂性相关材料时，我遇到了这个问题以及在某人的博客和某人的书中解决的示例。看到这个例子是相同的......

http://www.guru99.com/cyclomatic-complexity.html

http://books.google.pl/books?id=M-mhFtxaaskC&lpg=PA385&ots=jB8P0avJU7&d&hl=pl&pg=PR1#v=onepage&q&f=false -> 转到第 384 页

尽管如此，希望在某种程度上使这个问题对其他人有用。

算法

取自http://www.cs.swan.ac.uk/~csmarkus/CS339/dissertations/GregoryL.pdf：

  1. 计算程序图。
  2. 计算圈复杂度。
  3. 选择一组基本路径。
  4. 为每个路径生成测试用例

前两点有时可能会被折叠，因为计算复杂性可能不一定涉及图形构建。然而，对于基本路径集，您需要在脑海中至少初步勾勒出图表。

计算

要计算复杂性，您需要决定如何进行。

  1. 从图中，1.1。计数区域 1.2. 计算边、节点、出口点
  2. 从具有一个退出点的源代码，计算条件
  3. 从具有许多退出点的源代码，计算条件，减去退出点并加 2。

复杂度等于：

  • 区域数量-最好在图表中看到，我在其他 SO 问题上做了一个，所以将链接到那里而不是复制/粘贴
  • 边 - 节点 + 2 *（出口点）
  • Edges - Nodes + (exit points) // 提供强连通图
  • (Decision points) + 1 // 提供一个入口点，一个出口点
  • (决策点) - (退出点) + 2 // 许多退出点

决策点 = IF、FOR、WHILE ... 由于 `if (a OR/AND b) 等价于 if a 和/或 if b，复合条件将复杂度加 2，因此这种 if 的复杂度为 2（因为它是 2如果无论如何）。

示例图表和更多阅读链接：https ://stackoverflow.com/a/21658235/999165 。

基路径测试——白盒测试

McCabe 指出，复杂度数是线性独立电路的数字 - 通过代码的路径，因此它也是最小测试用例数。因此，您需要构建与您拥有的路径一样多的测试用例。路径是通过遍历图来选择的，因为它是一个迷宫：

从零处的路径计数器开始，并且： 1. 向左走直到汇节点（出口点） 2. 路径计数器 + 1 3. 再次向左走，在到达汇点之前的最低决策点，选择右而不是左 4. 重复步骤 1 - 3，直到所有决策点完全用尽

您遍历的节点构成您的路径。

http://en.wikipedia.org/wiki/Basis_path_testing

于 2014-02-09T11:22:11.743 回答