1      引子

软件复杂度直接关系到软件产品的可维护性，可信性和产品的质量。认识软件复杂度的重要性不言而喻，这篇文章我们就来学习和探讨一下软件的复杂度。 

2      软件复杂度 

软件复杂度强调的是软件系统本身包括软件和系统部署在内的可控性的难易程度。它涉及到了一个软件的众多属性，这些属性会影响到软件的内部实体之间的交互。随着实体数量的增加，它们之间相互作用的数量也会成倍地增加，最坏的情况是达到无法掌控和理解的程度。

软件的复杂程度越高，就会增加软件实体之间交互出错的风险，在进行修改时引入Bug的机会也会增加。在更极端的情况下，过高的复杂度会使得软件修改几乎不可能。 

2.1  度量方法

到目前为止，已经存在许多衡量软件复杂度的方法。其中的许多指标虽然能很好地表示复杂度，但并不容易测量。一些比较常用的度量标准是:

·        McCabe的循环复杂性度量

·        Halsteads软件科学指标

·        Henry和Kafura在1981年提出了"基于信息流的软件结构度量"，将复杂度作为扇入和扇出的函数来衡量。他们将一个过程的扇入（fan-in）定义为进入该过程的局部流的数量加上该过程从中检索信息的数据结构的数量。fan-out被定义为从该过程中流出的局部流的数量加上该过程更新的数据结构的数量。局部流与调用该过程或被该过程调用的过程所传递的数据有关。Henry和Kafura的复杂度值被定义为 "过程长度乘以fan-in的平方乘以fan-out的平方"(Length×(fan-in×fan-out)²)。

·        1994年，Chidamber和Kemererer在1994年提出了面向对象设计的度量套件，他们的重点是专门针对面向对象软件的度量。他们介绍了六种OO复杂度度量指标：每个类的加权方法、对象类之间的耦合、类的响应、子类的数量、继承树的深度和方法的凝聚力缺乏。

还有其他几个指标可以用来衡量软件复杂度：

·        分支复杂度(Sneed度量)

·        数据访问复杂度(卡片度量)

·        数据复杂度（查平度量）

·        数据流复杂度（Elshof度量）

·        决策复杂度（麦克卢尔度量） 

2.2  复杂度的类别 

   问题的复杂度可以分为类：

·          可消除的复杂度。

n  开发工具导致：一套更适合的开发工具或者更高级的软件语言可能会降低其复杂度。

n  开发能力导致：模块划分，架构设计，领域定义，代码编写等等。

·          必要的复杂性：是由被解决的问题本身的特点所决定的，无法减少。

2.3  环形复杂度的例子

环形复杂度是一种软件度量，用来计算程序的复杂度。它是对程序源代码中的线性独立路径的数量进行量化测量。它是由Thomas J. McCabe, Sr.在1976年提出的。

环形复杂度是用程序的控制流图来计算的：图中的节点对应于程序中不可分割的指令组，如果第二条指令在第一条指令之后立即执行，那么一条定向边就会连接这两个指令节点。环形复杂度也可以应用于程序中的单个函数、模块、方法或类。

环形复杂度也常常用来制定测试案例的数量。

2.3.1  计算方法

现在说一下环形复杂度的计算方法，上面是一个简单程序的控制流程图。程序从红色节点开始执行，然后进入一个循环（紧靠红色节点下面的三个节点组）。在退出循环时，有一个条件语句（循环下面的组），最后程序在蓝色节点处退出。这个图有9条边，8个节点，1个连接的分量，所以程序的环形复杂度为9-8+2*1=3。

与上述相同的函数，用替代方案表示，其中每个出口点与入口点相连。这个图有10条边，8个节点，1个连接的分量，使用替代方案(10 - 8 + 1 = 3)也会产生3的环形复杂度。

2.3.2  测试案例的数量

再看一个例子：

有如下代码：

if (c1())

    f1();

else

    f2();

if (c2())

    f3();

else

    f4();

上面是源码的控制流程图；红圈是函数的入口点，蓝圈是退出点。退出点与入口点相连，使图中的图形有了清晰的关联。

在这个例子中，两个测试用例足以实现完全的分支覆盖，而要实现完全的路径覆盖则需要四个测试用例。程序的环形复杂度为3（因为程序的强连接图包含9条边、7个节点和1个连接组件）（9-7+1）。

作为一个函数的例子，要想准确地测试它，需要的不仅仅是简单的分支覆盖，还要再考虑一下上面的函数，假设为了避免bug的发生，任何调用f1()或f3()的代码都必须同时调用另一个。假设c1()和c2()的结果是独立的，这意味着上面的函数包含一个bug。分支覆盖的标准我们只用两个测试案例来就够了，比如如下的测试集：

c1()返回true，c2()返回true。

c1()返回false，c2() 返回false。

但是这两种情况都不会暴露出上面这个bug。如果我们用环形复杂度来表示我们需要的测试数量，那么这个数字会增加到3。因此，我们必须测试以下路径中的一个：

c1()返回 true，c2() 返回false

c1()返回false，c2() 返回true

这些测试中的任何一个都会暴露出BUG。

3      参考

https://en.wikipedia.org/wiki/Programming_complexity

https://en.wikipedia.org/wiki/Human%E2%80%93computer_interaction

https://en.wikipedia.org/wiki/Halstead_complexity_measures

https://en.wikipedia.org/wiki/Software_metrics

https://en.wikipedia.org/wiki/Lehman%27s_laws_of_software_evolution

https://en.wikipedia.org/wiki/Software_crisis

https://en.wikipedia.org/wiki/Software_metric

https://en.wikipedia.org/wiki/Cyclomatic_complexity