程序复杂度之圈复杂度

圈复杂度（Cyclomatic complexity）也称为条件复杂度或循环复杂度，是一种软件度量，是由Thomas J. McCabe, Sr. 在 1976 年提出，用来表示程序的复杂度，其符号为 VG 或是 M。圈复杂度是对源代码中线性独立路径数的定量测量。

圈复杂度使用的程序的控制流图来计算：在图中的节点对应于程序中一组不可分割的命令[代码行]，有向边连接两个可连续执行的节点；[可连续执行的两个节点：第二个节点的命令组可能在第一个节点执行后立刻开始执行]。圈复杂度可以应用到独立的功能，模块，方法或类。

基础路径测试：通过测试用例测试程序中的每个线性无关的独立路径；在这种测试策略下，测试用例的数目将等于该程序的圈复杂度；

圈复杂度定义

圈复杂度度量的是程序中线性独立路径的数量；例如：如果程序中不包含控制、判断、条件语句（例如 if，swith 等），那么复杂度就是 1 ；因为整个程序只有一条执行路径；如果程序包含一条IF语句，那么就会有两条路径来执行完整个程序（IF为 TRUE，IF 为 FALSE），所以这时候的复杂度就是 2；两个嵌套的 IF 语句，或者包含两个判断条件的一个 IF 语句，复杂度就是 4；

在数学上，一个结构化程序的圈复杂度通过该程序的控制流图来定义；控制流图包含程序的基本块（图的节点），和两个基本块之间可执行性（图的边）。

原理：

上图：单程序的控制流图。此程序由红色的节点开始运行，然后进入循环（红色节点下由三个节点组成），离开循环后有条件分支，最后运行蓝色节点后结束，此控制流图中，E = 9, N = 8, P = 1，因此其圈复杂度为 9 - 8 + (2*1) = 3

数学表达式：

M = E - N + 2P

其中

强连通图的圈复杂度定义：要求做完线上功能的先要求线上的功能

上图：对应同一个程序的控制流图，但多加一个从结束点到启始点的边，因此为强连通的控制流图，若利用此图计算圈复杂度，其公式为 M=E-N+P，而 E = 10、N = 8、P = 1，因此圈复杂度为 3

M = E - N + P

上式可以视为计算图中线性独立回路（回路内不包括其他回路）的个数，由于控制流图增加结束点到启始点的边，因此对应一个结束点至少会有一个回路。

M = E - N + 2

圈复杂度可以适用于同时分析许多程序或副程序的情形（例如针对一个类中的所有方法），此时 P 等于程序的个数，因为每一个程序的图都是一个独立的连接组件。若每一个程序都只一个结束点，P 也可以视为是结束点的个数。

McCache 证明了任何只有一个进入点和一个技术点的结构化程序，其圈复杂度等于程序中决策点（IF，FOR loops）的个数加 1；

圈复杂度也可以延伸到多个结束点的程序，此时的圈复杂度如下：

π - s + 2

其中

s 为结束点的个数

圈复杂度应用

限制软件复杂度

评估软件的结构化程度 「structuredness」

Essential complexity (numerical measure of "structuredness")

启示软件测试工作

圈复杂度决定了需要多少个测试用来达到特定模块测试覆盖率要求；

模块内聚性的评估

推测软件缺陷个数

许多研究指出一模块及方法的圈复杂度和其中的缺陷个数有相关性，许多这类研究发现圈复杂度和缺陷个数有高度的正相关：圈复杂度最高的模块及方法，其中的缺陷个数也最多。

不过，有些研究是在控制模块大小相近的情形下进行分析（例如比较二个源代码行数相近，但圈复杂度不同模块的缺陷个数），许多这类的研究发现圈复杂度和缺陷个数没有明显相关，不过仍有一些研究认为在此情形下二者仍有相关性。有些此领域的研究者认为那些研究结果圈复杂度和缺陷个数没有明显相关的研究，其研究方法的有效性可能有问题。

莱斯·哈顿认为利用圈复杂度来预测缺陷个数，和利用源代码行数来预测缺陷个数的结果大致相近。

OneAPM Mobile Insight 以真实用户体验为度量标准进行 Crash 分析，监控网络请求及网络错误，提升用户留存。访问 OneAPM 官方网站感受更多应用性能优化体验，想阅读更多技术文章，请访问 OneAPM 官方技术博客。本文转自 OneAPM 官方博客