如何进行算法的复杂度分析?
前言
本篇文章收录于专辑:http://dwz.win/HjK
你好,我是彤哥,一个每天爬二十六层楼还不忘读源码的硬核男人。
大家都知道,数据结构与算法解决的主要问题就是“快”和“省”的问题,即如何让代码运行得更快, 如何让代码更节省存储空间。
所以,“快”和“省”是衡量一个算法非常重要的两项指标,也就是我们经常听到的时间复杂度和空间复杂度分析。
那么,为什么需要复杂度分析呢?复杂度分析的方法论是什么呢?
这就是我们本节要解决的问题。
好了,进入今天的学习吧。
为什么需要复杂度分析?
首先,我们来思考一个问题:对于两个算法,我们如何评判谁运行得更快,谁运行时更节省内存?
你可能会说,这还不简单,把这两个算法运行一遍,统计下运行时间和占用内存不就可以了吗?
没错,这确实是一种不错的方法,而且它还有个非常形象的名字:事后统计法。
但是,这种统计方法具有非常明显的问题:
-
不同的输入对结果影响很大
对于一些输入,可能算法A执行得更快;对于另外一些输入,可能算法B执行得更快。比如,我们后面要学习的排序算法,输入的有序性对于不同的排序算法的影响是完全不同的。
-
不同的机器对结果影响很大
对于同样的输入,可能在一台机器上算法A更快,而在另外一台机器上算法B更快。比如,算法A可以利用多核而算法B不能,那么CPU的核数对这两个算法的影响将截然不同。
-
数据规模对结果影响很大
当数据规模小时,可能算法A更快,而数据规模变大时,可能算法B更快。比如,我们后面要学习的排序算法,当数据规模比较小时,插入排序反而比归并排序更快。
所以,我们需要一种可以不用实际运行算法,就可以估计算法执行效率的方法。
这也就是我们所说的复杂度分析。
那么,怎么进行复杂度分析呢?有没有什么方法论呢?
还真有,这个方法论叫作渐近分析法。
什么是渐近分析法?
渐近分析法,是指将算法执行的效率与输入的规模进行挂钩,随着输入规模的增大,算法执行所需要的时间(或空间)将呈现一种什么样的趋势,这种趋势就叫作渐近,而这种方法就叫作渐近分析法。
概念可能比较拗口,我举个简单的例子,对于给定的一个有序数组,我要查找其中某个值所在的位置,比如,查找8这个元素,有哪些方法呢?
简单暴力点的方法,从头遍历,查找到该元素即返回。
更友好一点的方法,采用二分法,每次定位到数据的中间位置,看其值与目标值的大小,判断是在左边还是右边继续以二分的方式查找。
上面我们举的例子的输入规模是8个元素的有序数组,目标值为8,使用第二种方法明显比第一种方法要快很多。
但是,如果查找的目标是1呢?
对于第一种方法,查找一次足矣。
对于第二种方法,需要查找3次。
此时,第二种方法又次于第一种方法了。
所以,比较两个算法的执行效率,不能只考虑到个别元素,而应该顾及到所有元素的感受。
我们以数学的方法来统计两种方法的平均执行效率,假设输入规模扩展到n。
对于第一种方法,1号元素查找一次,2号元素查找两次,3号元素查找三次……,而查找每个元素的概率都是1/n。
所以,它的执行效率为:1x1/n + 2x1/n + 3x1/n + ... nx1/n = nx(n+1)/2/n = (n+1)/2。
对于第二种方法,中间的元素有一个,查找一次,次中间的元素有两个,查找两次,次次中间的元素有四个,查找三次...,每次查找的规模都缩小一半,而查找每个元素的概率都是1/n。
所以,它的执行效率为:1x1x1/n + 2x2x1/n + 4x3x1/n + ... + 2^(log2(n)-2) x (log2(n)-1) x 1/n+ 2^(log2(n)-1) x log2(n) x 1/n = ?
我了个去,这个结果等于多少?
是时候展现真正的实力了:
你可能要骂娘了,对于我一个小学毕业的,难道我没办法学习数据结构与算法了?
No,No,No,肯定不能这么玩,那么,应该怎么玩呢?我们下一节接着讲。
后记
本节,我们从算法执行效率方面阐述了为什么需要复杂度分析,并介绍了复杂度分析的方法,即渐近分析法,如果严格地遵循渐近分析法,需要大量的数学知识,这无疑增加了我们分析算法的难度,那么,有没有什么更省心地计算复杂度的方法呢?
关注公众号“彤哥读源码”,解锁更多源码、基础、架构知识!
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
xmake从入门到精通12:通过自定义脚本实现更灵活地配置
xmake是一个基于Lua的轻量级现代化c/c++的项目构建工具,主要特点是:语法简单易上手,提供更加可读的项目维护,实现跨平台行为一致的构建体验。 本文主要详细讲解下,如何通过添加自定义的脚本,在脚本域实现更加复杂灵活的定制。 项目源码 官方文档 配置分离 xmake.lua采用二八原则实现了描述域、脚本域两层分离式配置。 什么是二八原则呢,简单来说,大部分项目的配置,80%的情况下,都是些基础的常规配置,比如:add_cxflags, add_links等,只有剩下不到20%的地方才需要额外做些复杂来满足一些特殊的配置需求。 而这剩余的20%的配置通常比较复杂,如果直接充斥在整个xmake.lua里面,会把整个项目的配置整个很混乱,非常不可读。 因此,xmake通过描述域、脚本域两种不同的配置方式,来隔离80%的简单配置以及20%的复杂配置,使得整个xmake.lua看起来非常的清晰直观,可读性和可维护性都达到最佳。 描述域 对于刚入门的新手用户,或者仅仅是维护一些简单的小项目,通过完全在描述配置就已经完全满足需求了,那什么是描述域呢?它长这样: target("test")set...
- 下一篇
阿里巴巴泰山版《Java 开发者手册》,也是一份防坑指南
我是风筝,公众号「古时的风筝」。 文章会收录在 JavaNewBee 中,更有 Java 后端知识图谱,从小白到大牛要走的路都在里面。 4月22日,阿里巴巴发布了泰山版《Java 开发手册》,以前以为终极版就真的是终极版了,没想到还是想的太简单了,继终极版之后又发布了详尽版、华山版,这不,泰山版又来了。想想也对,行业一直在发展,JDK 也一直在更新,怎么可能有终极版。 自从2017年阿里发布终结版发布以来,我就把这个手册当做开发规范使用,放在电脑中最显眼的地方,时不时就翻出来看一看,并且在团队中推广,还顺便安利给了一些朋友。每次有新版本发布都第一时间拿下来再重新读一遍。 本次泰山版发布,对比上一版本有如下几个更新: 发布错误码统一解决方案。 新增 34条新规约,比如,日期时间的闰年、闰月问题,三目运算的自动拆箱,SQL 查询的表别名限定,Collectors 类的 toMap()方法使用注意等。 修改描述 90处,比如,阻塞等待锁、建表的小数类型等。 完善若干处示例,比如,ISNULL 的示例等 。 为什么要经常拿出来读一读呢? 手册涉及从项目设计到编码、部署的各个方面。但是对于开发者...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS7设置SWAP分区,小内存服务器的救世主
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- SpringBoot2全家桶,快速入门学习开发网站教程
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题