5 分钟了解下【圈复杂度】是如何计算的？

theme: cyanosis

这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战

圈复杂度用来衡量代码结构的复杂程度；

公式法

如图是一张简单的程序流程控制图：

程序由红色的节点开始运行，然后进入循环（红色节点下由三个节点组成），离开循环后有条件分支，最后运行蓝色节点后结束；

由此流程控制图，我们便可以开始计算该程序的 圈复杂度；

计算公式：M = E − N + 2*P

E 为图中边的个数，N 为图中节点的个数，P 为图中连通分量的个数。

此图中，E = 9, N = 8, P = 1，因该程序圈复杂度为 9 - 8 + (2*1) = 3 ；

边的个数和节点的个数很好理解，但：

什么是 连通分量？

• 原来，在无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图；

虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-V2-V3 和 V1-V4-V3，因此称 V1 和 V3 之间是连通的。

• 若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为 连通分量；如图示：

• 而在有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为 强连通图；
• 若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为 强连通分量。

注意：圈复杂度计算中，计算变量是连通分量，而不是强连通分量！

判定法

上面通过公式来计算圈复杂度，似乎有点太过麻烦，计算边、节点、连通分量，都要费不少劲！

有没有更加粗暴简单的方法呢？答案就是：判定法！

当程序遇到这些判定条件时，圈复杂度在原有基础上加 1 即可；

• if 语句
• while 语句
• for 语句
• case 语句
• catch 语句
• and 和 or 布尔操作
• ? : 三元运算符

接着以上节程序控制图为例，正常顺序的圈复杂度为 1，遇到 for 循环 +1，然后遇到 if 语句，再 +1 ，最后结果为 3；

怎样，是不是够粗暴简单？判定法用于简单程序的圈复杂度计算还是很有效果的；

需要注意的是：对于多分支的 case 结构或多个 if - else 结构，必须统计全部实际的判定条件数；

圈复杂度是评判代码优劣的标准之一，通常来说，圈复杂度不要大于 5 ，否则代码将会被判定为 不易读！

降低圈复杂度大致有如下方法：

• 简化、合并条件表达式
• 将条件判定提炼出独立函数
• 将大函数拆成小函数
• 以明确函数取代参数
• 替换算法

从先计算后降低圈复杂度的角度来优化代码，使代码更加易读、易扩展、易维护，这就叫【专业】！

我是掘金安东尼，公众号同名，输出暴露输入，技术洞见生活，下次再会~