数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?

王争 2018-09-26
我们都知道,数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢?这里就要用到我们今天要讲的内容:时间、空间复杂度分析。
其实,只要讲到数据结构与算法,就一定离不开时间、空间复杂度分析。而且,我个人认为,复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法的内容基本上就掌握了一半
复杂度分析实在太重要了,因此我准备用两节内容来讲。希望你学完这个内容之后,无论在任何场景下,面对任何代码的复杂度分析,你都能做到“庖丁解牛”般游刃有余。

为什么需要复杂度分析?

你可能会有些疑惑,我把代码跑一遍,通过统计、监控,就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢?这种分析方法能比我实实在在跑一遍得到的数据更准确吗?
首先,我可以肯定地说,你这种评估算法执行效率的方法是正确的。很多数据结构和算法书籍还给这种方法起了一个名字,叫事后统计法。但是,这种统计方法有非常大的局限性。
1. 测试结果非常依赖测试环境
测试环境中硬件的不同会对测试结果有很大的影响。比如,我们拿同样一段代码,分别用 Intel Core i9 处理器和 Intel Core i3 处理器来运行,不用说,i9 处理器要比 i3 处理器执行的速度快很多。还有,比如原本在这台机器上 a 代码执行的速度比 b 代码要快,等我们换到另一台机器上时,可能会有截然相反的结果。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(1117)

  • xr
    我不认为是多此一举,渐进时间,空间复杂度分析为我们提供了一个很好的理论分析的方向,并且它是宿主平台无关的,能够让我们对我们的程序或算法有一个大致的认识,让我们知道,比如在最坏的情况下程序的执行效率如何,同时也为我们交流提供了一个不错的桥梁,我们可以说,算法1的时间复杂度是O(n),算法2的时间复杂度是O(logN),这样我们立刻就对不同的算法有了一个“效率”上的感性认识。

    当然,渐进式时间,空间复杂度分析只是一个理论模型,只能提供给粗略的估计分析,我们不能直接断定就觉得O(logN)的算法一定优于O(n), 针对不同的宿主环境,不同的数据集,不同的数据量的大小,在实际应用上面可能真正的性能会不同,个人觉得,针对不同的实际情况,进而进行一定的性能基准测试是很有必要的,比如在统一一批手机上(同样的硬件,系统等等)进行横向基准测试,进而选择适合特定应用场景下的最有算法。

    综上所述,渐进式时间,空间复杂度分析与性能基准测试并不冲突,而是相辅相成的,但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序,所以在实际编程中,时刻关心理论时间,空间度模型是有助于产出效率高的程序的,同时,因为渐进式时间,空间复杂度分析只是提供一个粗略的分析模型,因此也不会浪费太多时间,重点在于在编程时,要具有这种复杂度分析的思维。

    作者回复: 写得很好。理解的到位

    2018-09-26
    14
    1128
  • 姜威
    总结
    一、什么是复杂度分析?
    1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
    2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
    3.分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。
    4.复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
    二、为什么要进行复杂度分析?
    1.和性能测试相比,复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
    2.掌握复杂度分析,将能编写出性能更优的代码,有利于降低系统开发和维护成本。
    三、如何进行复杂度分析?
    1.大O表示法
    1)来源
    算法的执行时间与每行代码的执行次数成正比,用T(n) = O(f(n))表示,其中T(n)表示算法执行总时间,f(n)表示每行代码执行总次数,而n往往表示数据的规模。
    2)特点
    以时间复杂度为例,由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势,所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响,所以在做时间复杂度分析时忽略这些项。
    2.复杂度分析法则
    1)单段代码看高频:比如循环。
    2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。
    3)嵌套代码求乘积:比如递归、多重循环等
    4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。
    四、常用的复杂度级别?
    多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括,
    O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)
    非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括,
    O(2^n)(指数阶)、O(n!)(阶乘阶)
    五、如何掌握好复杂度分析方法?
    复杂度分析关键在于多练,所谓孰能生巧。

    作者回复: 总结的很棒

    2018-09-26
    12
    730
  • 芳芳
    糟糕,是看不懂的感觉
    2018-09-26
    1
    242
  • 吕宁
    老师好,我们上算法课,老师讲到存储一个二进制数,输入规模(空间复杂度)是O(logn) bit。请问如何理解?

    作者回复: 比如8用二进制表示就是3个bit。16用二进制表示就是4个bit。以此类推 n用二进制表示就是logn个bit

    2018-09-26
    10
    161
  • Orcsir
    老师,代码片段把行号也写上吧。

    作者回复: 嗯嗯 我联系运营加上

    2018-09-26
    75
  • realEago
    看不懂别慌,也别忙着总结,先读五遍文章先,无他,唯手熟尔~

    作者回复: 说的太好了 我这里也没葵花宝典 学还是得靠自己

    2018-09-26
    2
    67
  • 起名好难
    文章里也说了,性能测试这种是受环境所影响的。作为程序员,我们能做的就是尽可能的降低复杂度,才能让代码在不同的环境下以最快的效率执行。至于是不是浪费时间,我觉得其实是个伪命题。首先按刚刚分析过程来看,通过熟悉练习,简单的代码是可以直接看出来复杂度的也就是不费时间;而比较复杂的代码就容易“一不小心”太“复杂”了,这个时候,为了代码质量考虑分析复杂度的时间也并不浪费。再有甚者,我们学习这个分析法,我觉得更多的是要明白这个理念,在写代码的时候就能关注一下这方面的问题,毕竟复杂的代码在写的过程往往是先分析整体逻辑结构的,并且写的过程也需要不断思考,了解这个理念后才能在写的过程中也思考关注这个点。不然,复杂的一段代码一旦写成,日后因为性能问题重构,更费时间。

    以上是对课后题的思考,欢迎批评指正☺。
    另: 感觉加法法则那个图,maxf(n)+g(n) 换成max(f(n)+g(n))会不会更好些?

    作者回复: 理解的非常透彻 非常有逻辑性 很赞。ps 图画错了 我联系运营改下

    2018-09-26
    52
  • halweg
    第二个例子中,第6.7行为什么是2n平方遍而不是n平方遍呢?

    作者回复: 因为两层循环 一层是n 两层是n*n。不信你自己令n=5 自己算算

    2018-09-26
    5
    41
  • 有一天
    一直有一个很纠结的问题,烦请解答一下:O具体是哪一个英文字母的缩写?

    作者回复: 不是英文缩写 就是一个数学符号而已

    2018-09-26
    2
    38
  • 最爱小黑黑
    睡前刷一遍 明早起来再细看一遍 加油各位!
    2018-09-26
    1
    38
  • scarlett
    回答 thinkings 的问题
    i=1;
    while (i <= n) {
    i = i * 2
    }
    假设n= 20,i每次的取值是2 4 8 16 执行4次,时间复杂度是O(log2n)
    i=1;
    while (i <= n) {
    i = i + 2
    }
    假设 n=20 i每次取值:3,5,7,9,11,13,15,17,19 ,执行9次,时间复杂度是O(n/2),根据老师讲的 公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略,所以是O(n)

    作者回复: 👍 分析的通俗易懂 棒棒哒

    2018-09-26
    4
    37
  • dickwxyz@126.com
    没有看懂,所以,我们只要知道 x 值是多少,就知道这行代码执行的次数了。通过 2x=n 求解 x 这个问题我们想高中应该就学过了,我就不多说了。 这里的x不就是代码里的n吗,时间复杂度不是O(n)吗?

    作者回复: i 第一次等于1
    第2次等于2
    第3次等于2*2
    第4次等于2*2*2
    .....
    第x次等于2的x-1次方
    ……
    那第几次之后等于n呢

    也就是2的x-1次方等于n求解x

    x粗略点讲就近似于logn

    也就是代码执行了logn遍就退出循环了

    所以根据大o标记法 为logn



    2018-09-26
    4
    30
  • Monday
    本节通读两遍,通俗易懂,对复杂度的概念有了新的认识。
    复杂度就是用来分析算法执行效率与数据规模之间增长关系。
    思考题,性能测试与复杂度分析不冲突,原因如下:
    1、性能测试是依附于具体的环境,如SIT、UAT机器配置及实例数量不一致结果也有差别。
    2、复杂度分析是独立于环境的,可以大致估算出程序所执行的效率。
    3、将复杂度熟记于心,能够写出更高效率、更好性能的代码。若某接口通过性能测试,达不到预期,还可以用复杂度分析接口代码,找出最影响性能的代码,进行优化。

    每段代码都分析一下时间复杂度、空间复杂度,是不是很浪费时间呢?
    这个问题分两种情况讨论
    1、开发过程中,码代码的过程中就能得出其复杂度,这并不会太多的浪费时间,同时只有分析了每段代码的复杂度,才能估算出它们的执行效率。
    2、优化代码时,只有在分析每段代码的复杂度后,才能定位问题代码,才能做相应优化

    另外提出两个问题:
    1、评论太多,也无法进行关键字搜索,一般没有时间爬楼全部看完,导致不同学友提出一样的问题
    2、评论太多,可能有些评论不正确,需要官方确认正确与否,以免误导学友。


    作者回复: 理解的很透彻!

    2018-09-26
    1
    26
  • 冯剑
    在分析多项式复杂度的时候,有根据输入规模确定复杂度O(m+n),我的理解是 假设n是相对比较大的值,那么这个复杂度O(m+n)<=O(2n),2是常量,这样的话复杂度不就是O(n),请问下,O(n)和O(m+n)的区别在什么地方?有什么应用场景能体现出二者不同
    2018-09-26
    3
    26
  • 陈华应
    有必要,基准测试是事后,也是理论验证,有时候O(n)未必一定比O(1)效率低。
           复杂度分析是理论,整体趋势上反应了一个算法的时间或者空间利用率与数据规模的渐进关系,并且像程序员之间使用设计模式来讨论代码设计一样,说出名字就大致知道代码是如何组织的,大O也是一样。
            随着自己使用大O分析代码复杂度的熟练程度增加,判断一段代码的复杂度可能分分钟的事情,甚至更快。

    作者回复: 理解的很透彻!

    2018-09-26
    18
  • Dwyane
    03
    大家好,这是我的总结:

    公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略
    1. 只关注循环执行次数最多的一段代码
    2.加法法则:总复杂度等于量级最大的那段代码的复杂度
    3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积


    只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们集作O(1)
    不同数据规模,无法评估 m 和 n 的量级大,所以不能利用加法法则,去掉某一个,而是 O(m+n)

    空间复杂度:表示算法的存储空间与数据规模之间的增加关系

    额外说一下:log3n 就等于 log32 * log2n 其实是利用换底公示推导,有疑问的搜一下。

    作者回复: 是换底公式 👍

    2018-09-26
    17
  • 短迪大魔王
    很有必要,现在是大数据时代,如果是矩阵计算,那就是on,如果是传统双for遍历那就是on²,做lr不依托矩阵都要天荒地老,那神经网络尤其是rnn就不用做了,即使是84万文本数据,长度为20个词,用单机gpu加速要跑七天。双for是几天那?经典例子是马踏棋盘,没优化代码跑几天,优化了又看不懂,问问老师如何对代码做优化,因为优化了就读不懂了有没有?
    空间复杂度也有必要,还是nlp的例子,如果是embending的话,内存开销和磁盘开销都小的多,虽然现在分布式允许无限大,但是生产环境要把数据传到hdfs,再传到训练集群上,这都有网络传输开销啊,其二是可能没有这个权限,不安全。其三,生成npy文件不能shuffle,很不便利,也不允许分割,所以事先要想好空间要怎么来。当然时间更重要,敏捷迭代。
    2018-09-26
    15
  • ChaoYrAx
    老师 空间复杂度 和时间复杂度的 具体区别是什么,我怎么看上去像一样的

    作者回复: 一个表示内存的消耗 一个表示执行的快慢

    2018-09-26
    15
  • 考研数据结构会考到🤓🤓
    2018-09-26
    14
  • huangjh
    有必要,性能测试更多的是一种实验结果。而复杂度分析,可以帮助我们分析内因。

    作者回复: 简洁到位!

    2018-09-27
    13
收起评论
99+
返回
顶部