数据结构与算法之美
王争
前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 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度

王争 2018-09-28
上一节,我们讲了复杂度的大 O 表示法和几个分析技巧,还举了一些常见复杂度分析的例子,比如 O(1)、O(logn)、O(n)、O(nlogn) 复杂度分析。掌握了这些内容,对于复杂度分析这个知识点,你已经可以到及格线了。但是,我想你肯定不会满足于此。
今天我会继续给你讲四个复杂度分析方面的知识点,最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized time complexity)。如果这几个概念你都能掌握,那对你来说,复杂度分析这部分内容就没什么大问题了。

最好、最坏情况时间复杂度

上一节我举的分析复杂度的例子都很简单,今天我们来看一个稍微复杂的。你可以用我上节教你的分析技巧,自己先试着分析一下这段代码的时间复杂度。
// n表示数组array的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) pos = i;
}
return pos;
}
你应该可以看出来,这段代码要实现的功能是,在一个无序的数组(array)中,查找变量 x 出现的位置。如果没有找到,就返回 -1。按照上节课讲的分析方法,这段代码的复杂度是 O(n),其中,n 代表数组的长度。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(702)

  • Alvin
    老师讲的很好,练习题最好是O(1),最差是O(n), 均摊是O(1)。

    看到好多人纠结于清空数组的问题: 对于可反复读写的存储空间,使用者认为它是空的它就是空的。如果你定义清空是全部重写为0或者某个值,那也可以!但是老师举的例子完全没必要啊!写某个值和写任意值在这里有区别吗,使用值只关心要存的新值!所以老师的例子,清空把下标指到第一个位置就可以了!

    作者回复: 嗯嗯 是的 多谢你。同学们帮把这一条顶上去吧 可以让其他同学都看看

    2018-09-28
    8
    1365
  • 阿杜S考特
    当i < len时, 即 i = 0,1,2,...,n-1的时候,for循环不走,所以这n次的时间复杂度都是O(1);
    当i >= len时, 即 i = n的时候,for循环进行数组的copy,所以只有这1次的时间复杂度是O(n);
    由此可知:
    该算法的最好情况时间复杂度(best case time complexity)为O(1);
    最坏情况时间复杂度(worst case time complexity)为O(n);
    平均情况时间复杂度(average case time complexity),
    第一种计算方式: (1+1+...+1+n)/(n+1) = 2n/(n+1) 【注: 式子中1+1+...+1中有n个1】,所以平均复杂度为O(1);
    第二种计算方式(加权平均法,又称期望): 1*(1/n+1)+1*(1/n+1)+...+1*(1/n+1)+n*(1/(n+1))=1,所以加权平均时间复杂度为O(1);
    第三种计算方式(均摊时间复杂度): 前n个操作复杂度都是O(1),第n+1次操作的复杂度是O(n),所以把最后一次的复杂度分摊到前n次上,那么均摊下来每次操作的复杂度为O(1)
    2018-09-28
    4
    390
  • 姜威
    总结

    一、复杂度分析的4个概念
    1.最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。
    2.最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。
    3.平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。
    4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

    二、为什么要引入这4个概念?
    1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
    2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

    三、如何分析平均、均摊时间复杂度?
    1.平均时间复杂度
    代码在不同情况下复杂度出现量级差别,则用代码所有可能情况下执行次数的加权平均值表示。
    2.均摊时间复杂度
    两个条件满足时使用:1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;2)低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。
    2018-09-28
    4
    249
  • 小白一只
    最好是O(1),最坏是O(n),平均平摊是O(1).


    不要纠结add和insert在哪儿被调用了。。。代码都写出来反而不好看。

    个人体会: 平均和平摊基本就是一个概念,平摊是特殊的平均。在分析时间复杂度是O(1)还是O(n)的时候最简单就是凭感觉,,,,,,,,出现O(1)的次数远大于出现O(n)出现的次数,那么平均平摊时间复杂度就是O(1)。。。。

    作者回复: 留言看似很平淡 但透漏着高手的气息。说的没错。高手就是凭感觉👍

    2018-09-29
    4
    245
  • jon
    看了大家的留言总结的很好,自己把练习题的答案整理了一下与大家分享:
    1. 最好情况时间复杂度为 O(1)
    2.最坏情况分析:
    最坏情况代码执行的次数跟每次数组的长度有关
    第1次调用insert的执行的次数为 n ,
    第2次调用insert的执行的次数为 2n ,
    第3次调用insert的执行的次数为 2^2 * n
    第k次调用insert的执行的次数为 2^(k-1) * n
    最坏时间复杂度为 O(n)。
    3. 平均情况分析
    当每次遇到最坏情况时数组会进行2倍扩容,原数组被导入新数组,虽然数组的长度变大了,但是插入操作落在的区间的长度是一样的,分别是0~len-1, len~(2len-1),....;
    插入的情况仍是len+1种:0~len-1和插满之后的O(len);所以每次插入的概率是:p= 1/len+1,
    最后求出加权平均时间复杂度为 1*p + 2*p+ ▪▪▪ + len*p + len * p = O(1) ;
    4. 均摊时间复杂度 O(1)
    而均摊复杂度由于每次O(len)的出现都跟着len次O(1),是前后连贯的,因而将O(len)平摊到前len次上,得出平摊复杂度是O(1)

    作者回复: 👍

    2018-10-01
    7
    80
  • 蝴蝶
    insert方法中有清空数组吗?抱歉,能指出哪行吗?真不明白😂

    作者回复: count=1;count被重置为1。之后再插入的数据就会覆盖掉原来的数据。就相当于将原数组清空了。并不需要显示的去清空

    2018-09-28
    1
    72
  • Stalary
    递归的时间复杂度怎么算呀

    作者回复: 这个话题有点大 要具体看了 重点应该分析递归调用的次数吧。然后再看每次调用的耗时。综合考虑

    2018-09-28
    1
    66
  • 赤身马可
    报告老师,我好像走错了教室。

    我是一个文科转行过来的菜鸟,刚刚学完Python,基本搞懂了“遍历”、“循环”、“判断”等概念。

    您开篇讲的课,我都基本都能明白,也提起了兴趣和信心,准备好好跟您学习。但这两次课听完,我又晕菜了。

    想请问一下,如果听不太懂(也可以去掉“太”),需要补哪些课?您能告诉我进入您课程的坡道和垫脚石么?有没有稍低一点年级的资料,让我可以补补课呢?

    还请抽时间回答,谢谢。

    作者回复: 嗯嗯,同学你好.

     你说了刚学完python,可能代码还没写熟练,所以我建议把python书上的所有实例代码都自己敲一遍,默写一遍。学编程,光看不写肯定是不行的。

    等你python代码写熟练了,你可以再开始学我这个专栏。 因为你没有数据结构和算法的基础,所以我建议,配合着《大话数据结构》《算法图解》两本书一块来学习。

    学习这个专栏的过程中,你可以把我讲到的数据结构和算法都用python代码实现一遍,如果实现不了,可以参照我放在Github上的代码,自己看懂之后,默写一遍。这个步骤非常锻炼你的编程能力,不要忽视!

    在学习专栏的过程中,不要一觉得看不懂就放弃,师傅领进门,修行靠个人。这里没有葵花宝典一样的捷径。学习还要靠自己。看不懂?那就自己多百度一下,看不懂也可以问问你同学、同事、学长,用一个星期来看一篇文章,狠下心来,别怕麻烦,不会学不会的。

    还有很多时候看不懂,你就硬着头皮看,都看完一遍,就会有感觉。之后再等有空了,再来看一遍,慢慢的都懂了。这门课很难,对于初学者来说,应该是计算机里最难的之一了,所以不要期望轻松就学会,这是不现实的。

    2018-09-29
    1
    65
  • Kealina.
    调皮一下,还请老师来衡量下这例子恰当不。

    举个栗子🌰:
    今天你准备去老王家拜访下,可惜老王的爱人叫他去打个酱油,她告诉你说她限时n分钟🕒给他去买。那么你想着以他家到楼下小卖部来回最多一分钟,那么 “最好的情况”就是你只用等他一分钟。那么也有可能遇到突发情况,比如说电梯人多吖,路上摔了一胶,天知道他去干了什么,用了n分钟,没办法👐,主上有令,n分钟限时,那这就是“最坏的情况”。难点,平均时间复杂度 就是他有可能是第1.2.3...n,中的某个分钟回来,那平均就是1+2+3+...n/n,把 所有可能出现的情况的时间复杂度 相加除以 情况数 。均摊的话就是把花时间多的分给花时间少的,得到一个中间值,所以说这就会和平均混淆,个人觉得主要还是概念不同。假如n是10分钟,那么9分钟分4分钟到1分钟那,8分3给2...,那均摊下来就是5分钟.编不下去了🤦🏼‍♀️

    作者回复: 哈哈,写的太好了。留言区卧虎藏龙啊~

    2018-10-04
    1
    53
  • Silence
    老师,加权平均值那个公式是怎么来的,每个的概率都是 1/2n,平均的不应该也是 1/2n 吗?为什么后面成了 2*(1/2n)+3*(1/2n)+.....n*(1/2n)+n*(1/2)
    2018-09-28
    4
    39
  • 天天向上
    高中的数学已经忘光了,又回去补了下, 现在将推导的结果分享给大家
    1、1+2+3+....+n+n 首先知道这是一个等差数列,等差数列的定义:每一项与前一个项的差都等于一个常数,这就是等差数列
    2、计算等差数列的求和公式: n(1+n)/2 ,这是一个已经推导出来的公式,至于怎么推导出来的,自行去学习吧
    好了, 现在开始推导:
    1、主要就是推导分子,1+2+3+...+n+n = n(1+n)/2 + n = n(1+n)+2n /2 = n+n²+2n/2 = n² + 3n /2 = n(n+3)/2
    2、将 n(n+3)/2 代入式子中,就成了 n(n+3)/2 / n+1 = n(n+3) /2(n+1)

    好了,打完收功
    2018-12-28
    6
    37
  • 张三丰
    1+2+3....+n+n / n+1 = n(n+3)/2(n+1) 老师这个公式怎么推导出来的 能一步步展示下吗

    作者回复: 公式是求平均比对多少个数组元素才能找到x。如果x再第一个位置,那需要1次比对,如果再第二个位置,就需要比对2次,一次类推,如果在第n个位置,就需要比对n次。如果不在数组中,也需要比对n次。所有的次数之和除以n+1中情况,就是平均比对元素个数。

    2018-09-29
    37
  • ppingfann
    课后题的最坏时间复杂度不应该是O(1)吗?按照上一节讲的,循环的次数如果是有限次,就算数量极大,那么也应该是O(1)不是吗?
    如果答案如大家所说的是O(n),那么原题的len=10这个初始条件就应该改写为len=n。

    作者回复: 因为len并不是个确定量 初始值是10而已

    2018-09-28
    3
    24
  • leo
    画的前两节思维导图:
    https://share.weiyun.com/5D2VFqS

    作者回复: 👍

    2018-09-29
    1
    22
  • 极客人哈哈
    第二个例子中,为什么是n+1次遍历?
    2018-09-28
    2
    12
  • 蝴蝶
    我算了下,最小是O(1),最大是O(n),平均和分摊都是O(1),对吗?😀

    作者回复: 是的 分析正确。不过我们一般情况下平均 均摊说一个就好了

    2018-09-28
    1
    12
  • 刘浩
    这道题按照老师所讲的 答案是 O(1),每次扩容的数量都是原来的2倍,都是经历之前数组长度的次数再次进行扩容,所以完全被均摊开了。

    但是老师我有一个问题,就是按照您讲的确实时间复杂度被均摊成了O(1),在这是一个理论的平均值,但终究不能忽略O(n)的存在,当n到达一定量级的时候,这个风险还是存在的,如果把他等同于O(1),真的没关系吗?

    作者回复: 你理解的很对啊,均摊只是其中一种复杂度度量方法,并不是说我们只关注均摊,不关注最坏。我们评价一段代码或者算法的时候,还是会综合这几种复杂度的。用什么表示复杂度不重要,初衷还是能更好的体现出这个算法或者代码的性能。

    2018-09-29
    11
  • AF
    最大的疑惑就是,insert()方法和add()方法是如何被调用的???
    2018-09-28
    1
    11
  • 木心
    老师,我是跨行学习Python。希望每次进步一点~早安(^O^)!
    2018-09-28
    11
  • 冷颜〆
    // array 表示一个长度为 n 的数组
     // 代码中的 array.length 就等于 n
     int[] array = new int[n];
     int count = 0;
     
     void insert(int val) {
        if (count == array.length) {
           int sum = 0;
           for (int i = 0; i < array.length; ++i) {
              sum = sum + array[i];
           }
           array[0] = sum;
           count = 1;
        }

        array[count] = val;
        ++count;
     }
    就这段代码而言 count=0
    怎么看时间复杂度都是O(1)啊 除非外面有循环一直运行 所以这段一直理解不了

    作者回复: 是一直循环调用insert

    2019-02-26
    3
    10
收起评论
99+
返回
顶部