循环复杂度
循环复杂度（Cyclomatic complexity）也称为条件复杂度或圈复杂度，是一种软件度量，是由老托马斯·J·麦凯布在1976年提出，用来表示程序的复杂度，其符号为VG或是M。循环复杂度由程序的原始码中量测线性独立路径的个数。此概念有些类似的量测文字复杂度的Flesch-Kincaid可读性测试 ，不过方法不完全相同。
循环复杂度是由程序的控制流图来计算：有向图的节点对应程序中个别的代码，而若一个程序执行后会立刻执行另一代码，会有边链接二代码对应的节点。圈复杂度可应用在程序的子程序、模块、方法或类别。
麦凯布首先提出一种称为“基础路径测试”（Basis Path Testing）的软件测试方式，是测试程序中的每一线性独立路径，此情形的测试用例个数即为程序的循环复杂度[1]。
“循环复杂度”的名称有时会让人误解，因为此复杂度不只计算程序中的循环（循环）个数。循环复杂度是指程序的控制流图中，若将结束点到启始点再增加一个边时，控制流图中的圈（几个边形成封闭路径）的个数[2]。
原理
[编辑]
一段程序的循环复杂度是其线性独立路径的数量。若程序中没有像IF指令或FOR循环的控制流程，因为程序中只有一个路径，其循环复杂度为1，若程序中有一个IF指令，会有二个不同路径，分别对应IF条件成立及不成立的情形，因此循环复杂度为2。
数学上，一个结构化程序[note 1]的循环复杂度是利用程序的控制流图来定义，控制流图是一个有向图，图中的节点为程序的基础模块，若一个模块结束后，可能会执行另一个模块，则用箭头链接二个模块，并标示可能的执行顺序。循环复杂度M可以用下式定义[2]：
- M = E − N + 2P
其中
- E 为图中边的个数
- N 为图中节点的个数
- P 为图中连通分量的个数
另一个计算循环复杂度的公式，需修改控制流图，每一个结束点都增加一个到启始点的边。修改后的图称为强连通，任何二个节点A和B，都可以找到从A到B及从B到A的路径。程序的循环复杂度等于此图中回路的个数（也称为第一贝蒂数），其公式如下[2]：
- M = E − N + P
上式可以视为计算图中线性独立回路（回路内不包括其他回路）的个数，由于控制流图增加结束点到启始点的边，因此对应一个结束点至少会有一个回路。
对于单一的程序（或副程序或方法），P恒为1。但循环复杂度可以适用于同时分析许多程序或副程序的情形（例如针对一个类别中的所有方法），此时P等于程序的个数，因为每一个程序的图都是一个独立的连接组件。若每一个程序都只一个结束点，P也可以视为是结束点的个数。
可以证明任何只有一个进入点及结束点的结构化程序，其循环复杂度等于程序中决策点（if指令及条件循环）个数加1[2][3]
循环复杂度也可以延伸到多个结束点的程序，此时的循环复杂度如下：
- π - s + 2
其中
应用
[编辑]限制软件复杂度
[编辑]麦凯布提出循环复杂度时，其原始目的之一就是希望在软件开发过程中就限制其复杂度。他建议程式设计者需计算其开发模块的复杂度，若一模块的循环复杂度超过10，需再分割为更小的模块[2]。NIST（国家标准技术研究所）的结构化测试方法论已此作法略作调整，在一些特定情形下，模块循环复杂度上限放宽到15会比较合适。此方法论也承认有些特殊情形下，模块的复杂度需要超过上述的上限，其建议为“模块的循环复杂度需在上限范围以内，否则需提供书面资料，说明为何此模块循环复杂度有必要超过上限。”[5]
模块内聚性的评估
[编辑]可以预期一个复杂度较高模块的内聚性会比较低，至少不会到功能内聚性的程度。一个有高复杂度及低内聚性的模块中会有许多的决策点，这类的模块多半执行超过一个明确定义的任务，因此内聚性较低。一个2005年的研究发现复杂度的度量和由专家评估的模块内聚性有高度负相关，反而针对内聚性设计的度量和专家评估结果之间的相关性还比较不明显[6]。
推测软件缺陷个数
[编辑]许多研究指出一模块及方法的循环复杂度和其中的缺陷个数有相关性，许多这类研究发现循环复杂度和缺陷个数有高度的正相关：循环复杂度最高的模块及方法，其中的缺陷个数也最多。
不过，有些研究是在控制模块大小相近的情形下进行分析（例如比较二个原始码行数相近，但循环复杂度不同模块的缺陷个数），许多这类的研究发现循环复杂度和缺陷个数没有明显相关，不过仍有一些研究认为在此情形下二者仍有相关性。有些此领域的研究者认为那些研究结果循环复杂度和缺陷个数没有明显相关的研究，其研究方法的有效性可能有问题[7]。
莱斯·哈顿认为利用循环复杂度来预测缺陷个数，和利用原始码行数来预测缺陷个数的结果大致相近[8]。
相关条目
[编辑]注解
[编辑]- ^ 此处的结构化特别强调一个函数只有单一的结束点
参考资料
[编辑]- ^ A J Sojev. Basis Path Testing. [2012-09-30]. （原始内容存档于2012-04-26）.
- ^ 2.0 2.1 2.2 2.3 2.4 McCabe. A Complexity Measure (PDF). IEEE Transactions on Software Engineering. December 1976: 308–320 [2012-10-01]. （原始内容 (PDF)存档于2022-05-30）.
- ^ 3.0 3.1 Belzer, Kent, Holzman and Williams. Encyclopedia of Computer Science and Technology. CRC Press. 1992: 367–368.
- ^ Harrison. Applying Mccabe's complexity measure to multiple-exit programs. Software: Practice and Experience (J Wiley & Sons). October 1984.
- ^ McCabe, Watson. Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric. 1996. （原始内容存档于2012-08-28）.
- ^ Stein; Cox, Glenn; Etzkorn, Letha; et al. Exploring the relationship between cohesion and complexity. Journal of Computer Science. 2005, 1 (2): 137–144 [2012-10-02]. doi:10.3844/jcssp.2005.137.144. （原始内容存档于2019-12-02）.
- ^ Kan. Metrics and Models in Software Quality Engineering. Addison-Wesley. 2003: 316–317. ISBN 0-201-72915-6.
- ^ Les Hatton. The role of empiricism in improving the reliability of future software. 2008. version 1.1. （原始内容存档于2012-11-03）.