圈复杂度

eslint 有个圈复杂度底配置，于是就顺便看了看。圈复杂度（Cyclomatic, CC），又称条件复杂度，是一种衡量代码复杂度底标准，其标记为 V(G) 。

相比于认知复杂度，圈复杂度更倾向于用数学模型来构建对代码复杂度底描述。与认知复杂度类似的是，圈复杂度越越高，程序出错底风险也就越大，其缺陷个数也可能越多。圈复杂度的说明程序代码底判断逻辑复杂，可能质量低，且难于测试和维护。

圈复杂度与出错风险

一般来说，圈复杂度大于 10 底方法存在很大的出错风险。

计算方法

任何一个程序都可以被表达为一个流程图，由此我们可以构建出一幅有向图。

1
2
3
4
5
6
7
8
9

+------+     +------+     +-----+
|  if  | --> | else | --> | end |
+------+     +------+     +-----+
  |                         ^
  |                         |
  v                         |
+------+                    |
| then | -------------------+
+------+

圈复杂度底计算公式为： V(G) = E - N + 2 ，其中 E 为边数， N 为节点数。

根据公式，我们可以得知，一个 if else 底圈复杂度为 V(G) = 4 - 4 + 2 = 2 。

我们再计算其他流程底圈复杂度。

1
2
3

+-------+     +-----+
| start | --> | end |
+-------+     +-----+

顺序流程， V(G) = 1 - 2 + 2 = 1 。

1
2
3
4
5
6
7
8
9

     +---------+     +-----+
  +> |  test   | --> | end |
  |  +---------+     +-----+
  |    |
  |    |
  |    v
  |  +---------+
  +- | process |
     +---------+

while 循环， V(G) = 3 - 3 + 2 = 2 。

不过这个计算也比较复杂，每次需要画流程图，圈复杂度有个更直观计算方法， V(G) = P + 1 ，其中， P 为被判定的节点数。

常见的被判定节点有：

• if
• while
• for
• case
• catch
• and 和 or 布尔操作
• 三元操作符

举个例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void sort(int *A)
{
  int i = 0;
  int n = 5;
  int j = 0;
  while (i < (n - 1)) 
  {
    j = i + 1;
    while (j < n) 
    {
      if (A[i] < A[j]) 
      {
        swap(A[i], A[j]);
      }
    }
    i = i + 1;
  }
}

有两个 while 和一个 if ，因此 V(G) = 2 * 1 + 1 + 1 = 1 。

1
2
3
4
5
6
7
8
9
10

int find (int match)
{
  for (int var in list) 
  {
    if (var == match && var != NAN) 
    {
      return var;
    }
  }
}

有一个 for ，一个 if ，一个 and ，因此 V(G) = 1 + 1 + 1 + 1 = 4 。

圈复杂度与认知复杂度

可以说，在经过简化之后，圈复杂度底计算相比认知复杂度要简单许多，但圈复杂度仍然面临一个问题：圈复杂度高的代码真的代码复杂程度高吗？举个简单的反例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int sumOfPrimes(int max) {
    int total = 0;
    for(int i = 1; i <= max; ++i) {
        for (int j = 2; j < i; ++j) {
            if (i % j == 0) {
                continue;
            }
        }
        total += i;
    }
    return total;
}
// 代码 1
// V(G) = 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14

String getWords(int number) {
    switch(number) {
        case 1:
          return "one";
        case 2:
          return "two";
        case 3:
          return "a few";
        default:
          return "lots";
    }
}
// 代码 2
// V(G) = 4

虽然以上两段代码，其圈复杂度相同，显然，代码 2 比代码 1 更易于理解。因此，认知复杂度的提出就是为了解决这个问题。但认知复杂度因此也就放弃圈复杂度简洁的计算模式，使得认知复杂度难于计算，而且认知复杂度也不能说完全解决了这个问题，双方各有优劣。

如何降低圈复杂度

常用的方法有：

• 简化、合并条件表达式
• 将条件判定提炼出独立函数
• 将大函数拆成小函数
• 以明确函数取代参数
• 替换算法
• 逆向表达
• 移除控制标记
• 以多态取代条件式
• 参数化方法

总的来说，降低圈复杂最重要的，不仅仅是缩减代码而将代码变得零碎，最重要的目的，是为了增加代码底自解释性。不然就又会从一个陷阱跳到另一个陷阱中去。但长代码的可读性总是很糟糕的，适当缩略代码是很必要的。