EEPW论坛

软件复杂度概述
----
　　　　　 　　　　北京旋极信息技术有限公司软件测试培训中心
　　在硬件的可靠性设计中，有一条基本原则“简单就是可靠”。这个原则同样也适合软件，与功能的增多或增强相伴的是不断升级与补丁。现在已经有若干种软件复杂性的度量方法可供参考，其中McCabe QA是比较出色和实用的方法，它能够计算出多种软件复杂度，由此可对软件进行检查、分析和查明那些可能导致错误的代码。

复杂度

　　70年代，软件系统已经变得极其复杂，无论是开发还是维护都是一项成本高昂的工作。人们意识到必须使软件模块化，以便于开发、测试和维护。为此，成立于1976的McCabe&Associates公司开发出了McCabe Cyclomatic Complexity Metric（圈复杂度）技术对软件进行结构测试。Metric以软件复杂度测量的数目为基础，能帮助工程师识别难于测试和维护的模块，圈复杂度已经成为评估软件质量的一个重要标准。人们可以用圈复杂度对软件的复杂度和质量进行衡量，来安排工程进度，在成本、进度和性能之间寻求平衡。

复杂度的种类

　　有模块、类和程序三类复杂度。模块复杂度包含了关于模块的复杂度信息；类复杂度是针对那些使用McCabe面向对象特性的程序，它包含了关于类的复杂度信息；程序复杂度包含了关于程序的复杂度信息。

集成复杂度报告

　　对应于三种复杂度的是三种复杂度报告。如果一个报告的复杂度信息不只一种，那么就把这些复杂度信息组合成新的报告。

　　集成复杂度信息只收集一个部件及其下级的信息。例如：如果一个程序级报告包含一个类复杂度，那么只报告组成程序的类的信息，而不包含类组成的信息。

McCabe复杂度

　　McCabe复杂度是对软件结构进行严格的算术分析得来的，实质上是对程序拓扑结构复杂性的度量，明确指出了任务复杂部分。McCabe复杂度包括：圈复杂度、基本复杂度、模块设计复杂度、设计复杂度、集成复杂度、行数、规范化复杂度、全局数据复杂度、局部数据复杂度、病态数据复杂度。

McCabe复杂度的用途

在软件工程中，有三种使用McCabe复杂性度量的方式。

　　作为测试的辅助工具。McCabe复杂性度量的结果等于通过一个子程序的路径数，因而需要设计同样多的测试案例以覆盖所有的路径。如果测试案例数小于复杂性数，则有三种情况一是需要更多的测试；二是某些判断点可以去掉；三是某些判断点可用插入式代码替换。

　　作为程序设计和管理指南。在软件开发中，需要一种简单的方式指出可能出问题的子程序。保持子程序简单的通用方法是设置一个长度限制，例如50行或2页，但这实际上是在缺乏测试简明性的有效方法时无可奈何的替代方法。不少人认为McCabe度量就是这样一种简明性度量。但是要注意，McCabe度量数大的程序，不见得结构化就不好。例如，Case语句是良结构的，但可能有很大的McCabe度量数（依赖于语句中的分支数），这可能是由于问题和解决方案所固有的复杂性所决定的。使用者应当自己决定如何使用McCabe度量所提供的信息。

　　作为网络复杂性度量的一种方法。Hall和Preiser提出了一种组合网络复杂性度量，用于度量可能由多个程序员组按模块化原理建立的大型软件系统的复杂性。他们提出的组合度量公式为

式中 C1,...,Ck是各个模块的复杂性；CN是网络复杂性；W1和W2为权值。

McCabe复杂度即可用于度量各个模块的复杂性，也可用于度量网络复杂性。



Cyclomatic Complexity (v(G))圈复杂度

　　圈复杂度是用来衡量一个模块判定结构的复杂程度，数量上表现为独立路径的条数，即合理的预防错误所需测试的最少路径条数，圈复杂度大说明程序代码可能质量低且难于测试和维护，经验表明，程序的可能错误和高的圈复杂度有着很大关系。

计算方法

　　节点是程序中代码的最小单元，边代表节点间的程序流。如果一个模块流程图有e条边n个节点，它的圈复杂度V(G)=e-n+2，典型的V(G)max=10。图1中示例的圈复杂度是2。

优点

　　避免软件中的错误倾向；指出极复杂模块，这样的模块也许可以进一步细化；度量测试计划，确定测试重点；在开发过程中通过限制程序逻辑，指导测试过程；指出将要测试的区域；帮助测试人员确定测试和维护对象；与所用的高级程序设计语言类型无关。

应用

　　圈复杂度指出为了确保软件质量应该检测的最少基本路径的数目。在实际中，测试每一条路经是不现实的，测试难度随着路径的增加而增加。但测试基本路径对衡量代码复杂度的合理性是很必要的。McCabe & Associates建议圈复杂度到10，因为高的圈复杂度使测试变得更加复杂而且增大了软件错误产生的概率。

提示：

　　圈复杂度度量是测量在一个软件模块中的分支数目，在所有的开发周期中都要使用。

　　圈复杂度度量以软件的结构流程图为基础。控制流程图描述了软件模块的逻辑结构。一个模块在典型的语言中是一个函数或子程序，有一个入口和一个出口，也可以通过调用/返回机制设计模块。软件模块的每个执行路径，都有与从模块的控制流程图中的入口到出口的节点相符合的路径。

　　“Cyclomatic”来源于非直接连接基本测试周期的数目，更重要的是，也通过直接相连的图表给出独立路径的数目。通过图表的相关性，一个节点可到达另一个节点。

　　圈复杂度度量也可作为模块基本流程图路径的数目，其重点在于模块线形组合后，所产生的路径数目是最小的。

对圈复杂度的限制

　　现在有许多好方法可以用来限制圈复杂度。过于复杂的模块容易出错，难于理解、测试、更正，所以应当在软件开发的各个阶段有意识地限制复杂度，许多开发者已经成功地实现把对软件复杂度的限制作为软件项目的一部分，尽管在确切的数目上略微有些争议。最初支持的数目是10，现在支持数目可达15。但是，只应当在条件较好的情况下使数目大于10，例如开发者非常有经验，设计合乎正式标准，使用现代化的程序语言、结构程序、代码预排和先进的测试计划。换句话说，开发团队可以选择超过10的限制数目，但是必须根据经验进行一些取舍，把精力花在比较复杂的模块上。



Essential Complexity (ev(G))基本复杂度

　　基本复杂度是用来衡量程序非结构化程度的，非结构成分降低了程序的质量，增加了代码的维护难度，使程序难于理解。因此，基本复杂度高意味着非结构化程度高，难以模块化和维护。实际上，消除了一个错误有时会引起其他的错误。

计算方法

　　将圈复杂度图中的结构化部分简化成一个点，计算简化以后流程图的圈复杂度就是基本复杂度。

优点

　　衡量非结构化程度；反映代码的质量；预测代码维护量，辅助模块划分；与所用的高级程序设计语言类型无关。

应用

　　当基本复杂度为1，这个模块是充分结构化的；当基本复杂度大于1而小于圈复杂度，这个模块是部分结构化的；当基本复杂度等于圈复杂度，这个模块是完全非结构化的。



Module Design Complexity (iv(G))模块设计复杂度

　　模块设计复杂度是用来衡量模块判定结构，即模块和其他模块的调用关系。软件模块设计复杂度高意味模块耦合度高，这将导致模块难于隔离、维护和复用。

计算方法

　　模块设计复杂度是从模块流程图中移去那些不包含调用子模块的判定和循环结构后得出的圈复杂度，因此模块设计复杂度不能大于圈复杂度，通常是远小于圈复杂度。

优点

　　衡量模块对其下层模块的支配作用；衡量一个模块到其子模块进行集成测试的最小数量；定位可能多余的代码；以复杂的计算逻辑和设计来区分模块；是设计复杂度（S0）和集成复杂度(S1)计算的基础；与所用的高级程序设计语言类型无关。



Design Complexity (S0)设计复杂度

　　设计复杂度以数量来衡量程序模块之间的相互作用关系，它提供了系统级模块设计复杂度的概况，有助于衡量进行自底向上集成测试的效果，而且提供了全面衡量程序设计规格和复杂度的数据，不反映独立模块的内部情况。高设计复杂度的系统意味着系统各部分之间有着复杂的相互关系，这样系统将难以维护。

S0是程序中所有模块设计复杂度之和，计算公式如下：



优点

　　可应用于完整的软件，也可应用于任何子系统；衡量代码的质量；指出一个模块整体的复杂度，反映了每个模块和其内部模块的控制关系；揭示了程序中模块调用的复杂度；有助于集成复杂度的计算。



Integration Complexity (S1)集成复杂度

　　集成复杂度是为了防止错误所必须进行的集成测试的数量表示，另一种说法是程序中独立线性子树的数目，一棵子树是一个有返回的调用序列。就像圈复杂度是测试路径的数目，而集成复杂度是程序或其子系统的独立线性子树。

计算方法

　　一个程序的集成复杂度和一个模块的圈复杂度是非常相似的，必须计算对程序进行完全测试所需集成测试的数目。S1的计算公式：

S1=S0-N+1

N是程序中模块的数目。

优点

　　有助于集成测试的实施；量化集成测试工作且反映了系统设计复杂度；有助于从整体上隔离系统复杂度。


Number of Lines (nl)行数

行数是模块中总的行数，包括代码和注释。

优点：

　　计算简单；与所用的高级程序设计语言类型无关；指出了模块的行数（即模块的规模），规模小的模块易于理解和维护。



Normalized Complexity (nv)规范化复杂度

规范化复杂度是圈复杂度除以行数。

计算方法

nv=v(G)/nl

优点

　　与所用的高级程序设计语言类型无关；定义那些有着显著判定逻辑密度的模块，这些模块相对于其他常见规范模块需要做更多的维护工作。



Global Data Complexity (gdv(G))全局数据复杂度

　　全局数据复杂度（需有McCabe Data）量化了模块结构和全局数据变量的关系，它说明了模块对外部数据的依赖程度，同时度量了全局数据的测试工作，也描述了模块之间的耦合关系，能反映潜在的维护问题。

　　对于如何跟踪全局数据使用情况的更多信息，可以参考《McCabe Data in Using McCabe IQ Add-Ons》。



Specified Data Complexity (sdv(G))局部数据复杂度

　　局部数据复杂度（需有McCabe Data）量化了模块结构和用户局部数据变量的关系，同时度量了局部数据的测试工作。

　　我们能够使用McCabe Data的数据字典选择单独的数据元素，指出每个数据元素具体的数据类型。局部数据复杂度还提供了其他的数据选择准则，量化了每个模块中相应数据对模块控制结构的影响。

　　关于数据字典的更多信息，参考文档《McCabe Data in Using McCabe IQ Add-Ons.》。



Pathological Complexity (pv(G))病态数据复杂度

　　病态数据复杂度衡量一个模块包含的完全非结构化成份的程度，标出向循环内部跳入的问题代码，而这些部分具有最大的风险度，通常需要重新设计。

计算方法

　　所有的非结构部分除去向循环内跳入的结构，转化为线结构，病态复杂度就等于简化以后流程图的圈复杂度。

优点

　　与所用的高级程序设计语言类型无关；指出了可靠性的问题，降低了维护风险；帮助识别极不可靠的软件。



Halstead Metrics（Halstead 复杂度）

　　McCabe QA能够为所选择的语言产生Halstead Metrics复杂度。Halstead复杂度是以程序中出现的运算符和运算元为计数对象，以它们出现的次数作为计数目标（直接测量指标），然后据以计算出程序容量、工作量。

优点

　　不要求对程序结构进行深层次分析；能够预测错误率；预测维护工作量；有利于项目规划，衡量所有程序的复杂度；计算方法简单；与所用的高级程序设计语言类型无关；众多研究结构研究表明Halstead复杂度对于预测程序工作计划和程序的Bug非常有用。



Line Count复杂度描述了Line Count复杂度并列出了它们的优点

Line Count Metrics（Line Count复杂度）

优点

　　软件物理规模的度量；定义了具体的Line Count数据，例如注释行和空行；协助指出难于理解的模块。