数据结构与算法之美
王争
前 Google 工程师
283751 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

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

add()
O(1)
摊还分析
insert()
O(n)
概率论
加权平均值
find()
O(n)
遍历整个数组
find()
O(1)
概率乘法法则
find()
示例代码
结论
分析方法
示例代码
结论
分析方法
示例代码
结论
分析方法
示例代码
结论
分析方法
示例代码
均摊时间复杂度
平均情况时间复杂度
最坏情况时间复杂度
最好情况时间复杂度
课后思考
内容小结
均摊时间复杂度
平均情况时间复杂度
最坏情况时间复杂度
最好情况时间复杂度
复杂度分析

该思维导图由 AI 生成,仅供参考

上一节,我们讲了复杂度的大 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/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

复杂度分析是算法设计中的重要概念,本文介绍了最好、最坏、平均、均摊时间复杂度的概念及计算方法。通过具体例子分析,帮助读者理解了这些概念。文章还介绍了均摊时间复杂度及其分析方法摊还分析,通过一个数组插入数据的例子详细解释了均摊时间复杂度的应用。作者强调了均摊时间复杂度的特殊性和应用场景,指出在特定场景下,均摊时间复杂度可以等同于最好情况时间复杂度。最后,文章总结了最好、最坏、平均、均摊时间复杂度的应用及复杂度分析方法,鼓励读者在后续学习中继续实践。整体而言,本文深入浅出地介绍了复杂度分析相关概念,为读者提供了全面的复杂度表示方法和分析思路。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(1193)

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

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

    2018-09-28
    32
    2592
  • 好吃二师兄
    最好是O(1),最坏是O(n),平均平摊是O(1). 不要纠结add和insert在哪儿被调用了。。。代码都写出来反而不好看。 个人体会: 平均和平摊基本就是一个概念,平摊是特殊的平均。在分析时间复杂度是O(1)还是O(n)的时候最简单就是凭感觉,,,,,,,,出现O(1)的次数远大于出现O(n)出现的次数,那么平均平摊时间复杂度就是O(1)。。。。

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

    2018-09-29
    21
    636
  • 赤身马可
    报告老师,我好像走错了教室。 我是一个文科转行过来的菜鸟,刚刚学完Python,基本搞懂了“遍历”、“循环”、“判断”等概念。 您开篇讲的课,我都基本都能明白,也提起了兴趣和信心,准备好好跟您学习。但这两次课听完,我又晕菜了。 想请问一下,如果听不太懂(也可以去掉“太”),需要补哪些课?您能告诉我进入您课程的坡道和垫脚石么?有没有稍低一点年级的资料,让我可以补补课呢? 还请抽时间回答,谢谢。

    作者回复: 嗯嗯,同学你好. 你说了刚学完python,可能代码还没写熟练,所以我建议把python书上的所有实例代码都自己敲一遍,默写一遍。学编程,光看不写肯定是不行的。 等你python代码写熟练了,你可以再开始学我这个专栏。 因为你没有数据结构和算法的基础,所以我建议,配合着《大话数据结构》《算法图解》两本书一块来学习。 学习这个专栏的过程中,你可以把我讲到的数据结构和算法都用python代码实现一遍,如果实现不了,可以参照我放在Github上的代码,自己看懂之后,默写一遍。这个步骤非常锻炼你的编程能力,不要忽视! 在学习专栏的过程中,不要一觉得看不懂就放弃,师傅领进门,修行靠个人。这里没有葵花宝典一样的捷径。学习还要靠自己。看不懂?那就自己多百度一下,看不懂也可以问问你同学、同事、学长,用一个星期来看一篇文章,狠下心来,别怕麻烦,不会学不会的。 还有很多时候看不懂,你就硬着头皮看,都看完一遍,就会有感觉。之后再等有空了,再来看一遍,慢慢的都懂了。这门课很难,对于初学者来说,应该是计算机里最难的之一了,所以不要期望轻松就学会,这是不现实的。

    2018-09-29
    14
    284
  • 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
    28
    182
  • 蝴蝶
    insert方法中有清空数组吗?抱歉,能指出哪行吗?真不明白😂

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

    2018-09-28
    7
    115
  • 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
    10
    110
  • Stalary
    递归的时间复杂度怎么算呀

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

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

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

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

    作者回复: 👍

    2018-09-29
    2
    31
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部