17 | 时间和空间复杂度（下）：如何使用六个法则进行复杂度分析？
黄申
该思维导图由 AI 生成，仅供参考
你好，我是黄申，今天我们接着聊复杂度分析的实战。
上一讲，我从数学的角度出发，结合自身经验给你总结了几个分析复杂度的法则。但是在实际工作中我们会碰到很多复杂的问题，这个时候，正确地运用这些法则并不是件容易的事。今天，我就结合几个案例，教你一步步使用这几个法则。
案例分析一：广度优先搜索
在有关图遍历的专栏中，我介绍了单向广度优先和双向广度优先搜索。当时我提到了通常情况下，双向广度优先搜索性能更好。那么，我们应该如何从理论上分析，谁的效率更高呢？
首先我们来看单向广度优先搜索。我们先快速回顾一下搜索的主要步骤。
第一步，判断边界条件，时间和空间复杂度都是 O(1)。
第二步，生成空的队列。常量级的 CPU 和内存操作，根据主次分明法则，时间和空间复杂度都是 O(1)。
第三步，把搜索的起始结点放入队列 queue 和已访问结点的哈希集合 visited，类似上一步，常量级操作，时间和空间复杂度都是 O(1)。
第四步，也是最核心的步骤，包括了 while 和 for 的两个循环嵌套。
我们首先看时间复杂度。根据四则运算法则，时间复杂度是两个循环的次数相乘。对于嵌套在内的 for 循环，这个次数很好理解，和每个结点的直接连接点有关。如果要计算平均复杂度，我们就取直接连接点的平均数量，假设它为 m。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文通过案例分析介绍了六个复杂度分析法则的实际运用。以搜索引擎为例，作者详细讨论了时间和空间复杂度的权衡。通过对全文搜索的两种处理方式进行分析，阐述了如何通过倒排索引来降低搜索引擎的时间复杂度，以及相应的空间复杂度。文章强调了在实际项目中，复杂度分析的重要性，以及如何避免资源浪费。通过具体案例分析，读者可以快速了解复杂度分析的实际应用，以及在不同情况下的复杂度变化。整体而言，本文以简洁清晰的语言，帮助读者理解复杂度分析的实际运用，以及在不同情况下的复杂度变化。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《程序员的数学基础课》，新⼈⾸单¥68
《程序员的数学基础课》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(11)
- 最新
- 精选
zzz老师的课非常棒，每篇都干货满满，收获很多，这些年的工作常常过于关注业务逻辑的实现（也与工作岗位和性质有关），忽略了技术和数学知识沉淀，最近看了老师的文章，有种回到学生时代的感觉，同时觉得这些知识真的很重要，有了这些知识的了解和沉淀，工作中在解决问题时一旦能够回忆起来，那么将是区别于普通程序员的体现，也是成就感和快乐之所在，值得反复阅读和练习。点赞。作者回复: 感谢支持，后面会继续提供实用的内容
2019-02-2311
qinggeouye案例一，广度优先搜索的时间复杂度，第 I 次 while 循环，这里的 I 可以认为是起始的那个搜索节点的最大度数？作者回复: 确实每个结点的度数都不同，我们通常考虑平均结点数。如果是最坏时间复杂度，我们也会用最大的度数。
2019-03-034
建强思考题： 平时工作中，和数据库打交道比较多点，性能分析和优化主要集中在对SQL语句的优化，一般通过SQL语句的执行计划，可以大致看出语句的搜索算法，虽然运用分析工具可以看出每一步的耗时情况，但如果结合老师讲的复杂度分析方法，对SQL语句的性能分析会更精准一点。作者回复: 确实，例如数据库是否有加索引，用的什么算法进行的索引，都有讲究
2020-03-182
escray
我在之前分析双向广度有限搜索的复杂度的时候，没有考虑到 a 和 b 两个节点的度相差比较大的情况。 平时似乎没有遇到与性能分析相关的项目，如果遇到了性能的瓶颈，一般来说，加硬件是比较容易的部分——内存、SSD，上更多的服务器。 其实这应该是算法分析的核心部分，六个法则加上最好、最差、平均情况的综合判断，需要经验积累。作者回复: 看了你最近的几个回复，都是很好的总结
2020-02-122- marcus1877我有个问题，不知道现在还有人能回答不？ “如果单向需要走 l 条边，那么双向是 l/2”。为什么双向是I/2？
作者回复: 这里l是字母l，表示所要走的边数，原文要表达的意思是，在双向中，每个出发结点所要走的边数是l/2
2020-12-2621 
总统老唐“查看b是否在这m个节点中，时间复杂度为O(1)”，怎么不是O(m)呢？作者回复: 可以使用哈希来做，当然哈希数据结构需要更多的存储空间，是拿空间换时间
2019-11-2821- 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-122- 013923谢谢老师！2022-07-28归属地：北京1
- Paul Shan对于不平均的双向广度遍历可以用更均衡一点的方法，也就是按照大学推进。例如左边平均连接的点数2事情，右边连接的点数是8.可以左边推进3层右边推进1层的进度进行，最终取得的效果是左右访问的点数差不多，这样总的访问点数最少（往左右移一层，新增的点数都大于减少的点数）。2019-08-281
收起评论
