程序员的数学基础课
黄申
LinkedIn 资深数据科学家
83374 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 58 讲
导读 (1讲)
基础思想篇 (18讲)
程序员的数学基础课
15
15
1.0x
00:00/00:00
登录|注册

17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?

空间复杂度分析
时间复杂度分析
时间复杂度分析
时间复杂度分析
判断是否找到通路的方式
双向搜索所要走的边数
while和for循环嵌套
将起始结点放入队列和哈希集合
生成空的队列
判断边界条件
倒排索引的空间复杂度
倒排索引概念
对全文进行分词
全文作为字符串
不均匀数据情况分析
时间复杂度分析
关键点
步骤分析
引入倒排索引
两种搜索方式
双向广度优先搜索
单向广度优先搜索
案例分析二:全文搜索
案例分析一:广度优先搜索
思考题
实战复杂度分析
时间和空间复杂度

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

你好,我是黄申,今天我们接着聊复杂度分析的实战。
上一讲,我从数学的角度出发,结合自身经验给你总结了几个分析复杂度的法则。但是在实际工作中我们会碰到很多复杂的问题,这个时候,正确地运用这些法则并不是件容易的事。今天,我就结合几个案例,教你一步步使用这几个法则。

案例分析一:广度优先搜索

在有关图遍历的专栏中,我介绍了单向广度优先和双向广度优先搜索。当时我提到了通常情况下,双向广度优先搜索性能更好。那么,我们应该如何从理论上分析,谁的效率更高呢?
首先我们来看单向广度优先搜索。我们先快速回顾一下搜索的主要步骤。
第一步,判断边界条件,时间和空间复杂度都是 O(1)。
第二步,生成空的队列。常量级的 CPU 和内存操作,根据主次分明法则,时间和空间复杂度都是 O(1)。
第三步,把搜索的起始结点放入队列 queue 和已访问结点的哈希集合 visited,类似上一步,常量级操作,时间和空间复杂度都是 O(1)。
第四步,也是最核心的步骤,包括了 while 和 for 的两个循环嵌套。
我们首先看时间复杂度。根据四则运算法则,时间复杂度是两个循环的次数相乘。对于嵌套在内的 for 循环,这个次数很好理解,和每个结点的直接连接点有关。如果要计算平均复杂度,我们就取直接连接点的平均数量,假设它为 m。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文通过案例分析介绍了六个复杂度分析法则的实际运用。以搜索引擎为例,作者详细讨论了时间和空间复杂度的权衡。通过对全文搜索的两种处理方式进行分析,阐述了如何通过倒排索引来降低搜索引擎的时间复杂度,以及相应的空间复杂度。文章强调了在实际项目中,复杂度分析的重要性,以及如何避免资源浪费。通过具体案例分析,读者可以快速了解复杂度分析的实际应用,以及在不同情况下的复杂度变化。整体而言,本文以简洁清晰的语言,帮助读者理解复杂度分析的实际运用,以及在不同情况下的复杂度变化。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《程序员的数学基础课》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(11)

  • 最新
  • 精选
  • zzz
    老师的课非常棒,每篇都干货满满,收获很多,这些年的工作常常过于关注业务逻辑的实现(也与工作岗位和性质有关),忽略了技术和数学知识沉淀,最近看了老师的文章,有种回到学生时代的感觉,同时觉得这些知识真的很重要,有了这些知识的了解和沉淀,工作中在解决问题时一旦能够回忆起来,那么将是区别于普通程序员的体现,也是成就感和快乐之所在,值得反复阅读和练习。点赞。

    作者回复: 感谢支持,后面会继续提供实用的内容

    2019-02-23
    11
  • qinggeouye
    案例一,广度优先搜索的时间复杂度,第 I 次 while 循环,这里的 I 可以认为是起始的那个搜索节点的最大度数?

    作者回复: 确实每个结点的度数都不同,我们通常考虑平均结点数。如果是最坏时间复杂度,我们也会用最大的度数。

    2019-03-03
    4
  • 建强
    思考题: 平时工作中,和数据库打交道比较多点,性能分析和优化主要集中在对SQL语句的优化,一般通过SQL语句的执行计划,可以大致看出语句的搜索算法,虽然运用分析工具可以看出每一步的耗时情况,但如果结合老师讲的复杂度分析方法,对SQL语句的性能分析会更精准一点。

    作者回复: 确实,例如数据库是否有加索引,用的什么算法进行的索引,都有讲究

    2020-03-18
    2
  • escray
    我在之前分析双向广度有限搜索的复杂度的时候,没有考虑到 a 和 b 两个节点的度相差比较大的情况。 平时似乎没有遇到与性能分析相关的项目,如果遇到了性能的瓶颈,一般来说,加硬件是比较容易的部分——内存、SSD,上更多的服务器。 其实这应该是算法分析的核心部分,六个法则加上最好、最差、平均情况的综合判断,需要经验积累。

    作者回复: 看了你最近的几个回复,都是很好的总结

    2020-02-12
    2
  • marcus1877
    我有个问题,不知道现在还有人能回答不? “如果单向需要走 l 条边,那么双向是 l/2”。为什么双向是I/2?

    作者回复: 这里l是字母l,表示所要走的边数,原文要表达的意思是,在双向中,每个出发结点所要走的边数是l/2

    2020-12-26
    2
    1
  • 总统老唐
    “查看b是否在这m个节点中,时间复杂度为O(1)”,怎么不是O(m)呢?

    作者回复: 可以使用哈希来做,当然哈希数据结构需要更多的存储空间,是拿空间换时间

    2019-11-28
    2
    1
  • cwtxz
    学习了老师的“使用六个法则进行复杂度分析”,让我对算法的复杂度分析不再那么一头雾水。以前在看算法书籍、看算法相关例题的时候,对于给出的程序,看倒是能够看懂,但是叫我进行算法复杂度分析,完全就是无从下手。说白了,自己是完全不懂算法复杂度分析的概念,又何谈进行算法复杂度分析。现在,有了老师的指导,至少有了一个进行复杂度分析的方向,不再是那么迷茫,至少我能能尝试着对一些简单的程序进行量化分析了。于我而言,通过这种分析,我能够将自己的代码进行性能调优,使自己的编程水准再上一个台阶。感谢老师,我会继续加油的!!!

    作者回复: 很高兴对你有所帮助☺️

    2020-01-04
  • l c
    双向广搜的特殊情况时间复杂度,ab的大小并不影响其搜索深度即l,而会影响底数即m。假如全平均情况为m,a < b情况为 x, y, 既然是特殊情况,不妨令 x < m < y,则a b的特殊情况时间复杂度都会向广度更高的一方偏斜,即结果为O(y^(l/2))).
    2020-07-12
    2
  • 013923
    谢谢老师!
    2022-07-28归属地:北京
    1
  • Paul Shan
    对于不平均的双向广度遍历可以用更均衡一点的方法,也就是按照大学推进。例如左边平均连接的点数2事情,右边连接的点数是8.可以左边推进3层右边推进1层的进度进行,最终取得的效果是左右访问的点数差不多,这样总的访问点数最少(往左右移一层,新增的点数都大于减少的点数)。
    2019-08-28
    1
收起评论
显示
设置
留言
11
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部