理解圈复杂度

Question

我最近遇到了圈复杂度，我想尝试更好地理解它。

在计算复杂度时，有哪些不同因素的实用编码示例？具体来说，对于维基百科的M = E − N + 2P方程，我想更好地理解以下每一个术语的含义：

• E=图的边数
• N=图的节点数
• P=连通分量数

我怀疑E或N可能是代码块中的决策点 (如果、如果、foreach等)的数量，但我不太确定哪个是哪个或另一个代表什么。我还猜测P是指函数调用和类实例化，但考虑到我所看到的，没有一个明确的定义。如果有人能用每个示例的一些清晰的代码示例来提供更多的信息，这将有所帮助。

作为后续，圈复杂度是否与100% 路径覆盖所需的单元测试数量直接相关？例如，一个复杂度为4的方法是否表示需要4个单元测试来覆盖该方法？

最后，正则表达式是否会影响圈复杂度，如果会的话，如何影响？

Answer 1

关于公式:节点表示状态，边缘表示状态更改。在每个程序中，语句都会带来程序状态的变化。每个连续语句都由一个边表示，程序的状态在(或之前)语句的执行是节点。

如果您有一个分支语句(例如，if)，那么将有两个节点出现，因为状态可以通过两种方式改变。

计算圈复杂度数(CCN)的另一种方法是计算执行图中有多少“区域”(其中“独立区域”是一个不包含其他圆的圆)。在这种情况下，CCN将是独立区域的数目加上1(与前面的公式所给出的数字完全相同)。

CCN用于分支覆盖，或路径覆盖，这是相同的。CCN等于在单个线程应用程序中理论上可能存在的不同分支路径的数量(其中可能包括"if x < 2 and x > 5 then“这样的分支，但是好的编译器应该将其作为不可访问的代码捕获)。您必须至少有那么多不同的测试用例(可能更多，因为一些测试用例可能重复前面的路径，但前提是每个测试用例都包含一个路径)。如果您无法用任何可能的测试用例覆盖路径--您发现了不可访问的代码(尽管您需要向自己证明为什么它是不可访问的，可能是某个隐藏在某个地方的嵌套x < 2 and x > 5 )。

至于正则表达式--当然，它们会影响到，就像其他代码一样。但是，regex结构的CCN可能太高，无法在单个单元测试中覆盖，您可以假设regex引擎已经过测试，而忽略表达式的分支潜力以满足测试需求(当然，除非您正在测试regex引擎)。

Answer 2

作为后续，圈复杂度是否与100%路径覆盖所需的单元测试数量直接相关？

是的，基本上。利用圈复杂度作为何时重构的指标也是个好主意。根据我的经验，对于较低的CC，可测试性和可重用性大大提高(尽管您应该是实际的-不要过度重构，而且某些方法由于它们的本质而具有很高的CC -尝试将其降低并不总是有意义的)。

最后，正则表达式是否会影响圈复杂度，如果会的话，如何影响？

是的，如果您想要准确的话，尽管大多数代码分析工具似乎并没有以这种方式考虑它们。正则表达式只是有限状态机，所以我猜它们的CC可能是从FSM图中计算出来的，但是它会是一个相当大的数目。