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

简介: 5 分钟了解下【圈复杂度】是如何计算的?

image.png

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


公式法



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

image.png


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


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

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

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

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

边的个数和节点的个数很好理解,但:


什么是 连通分量

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

image.png


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

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

image.png


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

image.png


注意:圈复杂度计算中,计算变量是连通分量,而不是强连通分量!


判定法



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


有没有更加粗暴简单的方法呢?答案就是:判定法!

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


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


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


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

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


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


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

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


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


相关文章
|
5月前
|
开发者
软件设计与架构复杂度问题之McCabe圈复杂度的定义如何解决
软件设计与架构复杂度问题之McCabe圈复杂度的定义如何解决
|
5月前
|
测试技术
圈复杂度问题之什么是“气功波”式代码,它有什么问题,如何解决
圈复杂度问题之什么是“气功波”式代码,它有什么问题,如何解决
|
5月前
圈复杂度问题之重构后的代码与原始代码相比有哪些提升
圈复杂度问题之重构后的代码与原始代码相比有哪些提升
|
Cloud Native 安全 Java
代码圈复杂度治理小结
我们一直在说系统很复杂,那到底什么是系统复杂度呢?作为团队的稳定性底盘负责人,也经常和大家探讨为什么会因为圈复杂度高而被扣分。那么,怎么才能写的一手可读,可扩展,可维护的好代码?本文作者尝试结合在团队内部的实践,分享下过程中心得。
代码圈复杂度治理小结
|
8月前
|
算法 前端开发 JavaScript
降低代码圈复杂度优化技巧
降低代码圈复杂度优化技巧
142 0
|
机器学习/深度学习 算法
【5分钟paper】基于近似动态规划的学习、规划和反应的集成架构
【5分钟paper】基于近似动态规划的学习、规划和反应的集成架构
167 0
|
搜索推荐 算法
认识复杂度和简单排序算法
认识复杂度和简单排序算法
84 0
【C#编程最佳实践 十一】降低圈复杂度最佳实践
【C#编程最佳实践 十一】降低圈复杂度最佳实践
146 0
|
算法 搜索推荐 Shell
一篇文章带你整体把控算法中的基本问题《排序
排序 本篇文章对算法中的基本问题--排序 的思想进行了描述,后续文章会对所有排序算法进行实现,欢迎关注本系列。 可以转载,但请声明源链接:文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
90 0

热门文章

最新文章