16 | 时间和空间复杂度（上）：优化性能是否只是“纸上谈兵”？
该思维导图由 AI 生成，仅供参考
基本概念
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了时间和空间复杂度的重要性以及系统性的复杂度分析方法。作者将系统性能影响因素分为算法理论上的计算复杂度、开发实现的方案和硬件设备的规格，并通过生产汽车的比喻强调了复杂度分析对性能评估的重要性。在基本概念部分，作者介绍了算法复杂度、时间复杂度和空间复杂度的概念，并强调了渐进时间复杂度和渐进空间复杂度的重要性。此外，作者总结了四则运算法则、主次分明法则和齐头并进法则，帮助读者快速、准确地进行复杂度分析。通过丰富的例子和详细的解释，读者可以更好地理解复杂度分析的方法和规则。文章通俗易懂，适合程序员快速了解复杂度分析的重要性和方法。文章还介绍了排列组合法则、一图千言法则和时空互换法则，以及它们在复杂度分析中的应用。总之，本文通过深入浅出的方式，系统性地介绍了复杂度分析的重要性和方法，对读者进行了全面而深入的指导。
《程序员的数学基础课》，新⼈⾸单¥68
全部留言(13)
- 最新
- 精选
- pyhhou思考题感觉要根据具体图的情况来看具体时间复杂是多少，就之前的六度关系的例子，假设把关系看作是一个树，每个结点都有 n 个子结点，要确认两个人是几度好友，也就是确认两个结点相距多少层，如果是单向广度优先搜索，时间复杂度 O(n^degree)，双向可以运用加法法则，两边同时出发，时间复杂度 2 * O(n^(degree/2))，空间复杂度是队列中暂存的结点的最大值，和时间复杂度一样
作者回复: 是的
2019-03-1612 
Being老师，我想了很久，不能确定，双向BFS的停止条件跟maxDegrees有关，也就是说最坏的情况是刚好到maxDgrees时搜索到，所以时间复杂度应该是 maxDgrees * 2*（V+E），运用四则运算法则，这个队列循环了maxDgrees次，每一次对node的访问都是（V+E），而双向是两端并进所以乘2，再根据主次分明，将常量这些去掉，最后就是O（V）。 空间复杂度也和maxDegrees有关，队列有两个maxDegrees*（V+E），visited的容器也有两个，同样的，主次分明来说，其他的变量就可以忽略了，然后用四则运算法则来计算，就是相加，最后是O（V） 以上都是算的最坏情况，最好情况是O（1），平均情况? 最后跟最坏情况一样，是使用排列组合法则推导吗？我后面再试试。作者回复: 分析的很详细👍，这里E是指边的数量？V是指结点的数量？
2019-01-195
炎发灼眼老师，有一点不明白，为什么在计算归并的复杂度时，切分的复杂度就是按照节点来算，是算每次切的时间么？而归并的时候是算指数的，合并的时候，其实也是两个节点合并一个，应该是按照合并的数目来算的。作者回复: 你这里的归并是指归并排序，对吧？归并排序的时间复杂度是O(n * logn)，其中logn表示二叉树的高度，而n表示二叉树的每一层，你都要扫描一遍长度为n的数组
2019-10-103- 冉冉“ 在数据归并阶段，我们看二叉树的高度，为 log2n，因此归并的次数为 log2n ” 为什么是看二叉树高度呢？我觉得归并次数应该和切分次数一样，都是看非叶子结点的个数吧？
作者回复: 是这样，每一层非叶子结点里所包含的数据集大小不同，如果按照非叶子结点数量来算不方便，好在不管怎样，每一层总的计算次数都是n（n是整个被排序数组的大小），所以在计算时间的时候，咱们只看层数log2n，时间复杂度是n x log2n
2020-09-232 
拉普达考虑图的平均节点度是d，平均最短路径（假设为无权图）为D。时间复杂度为O(D*d/2),O(d＾(D/2)*2)。作者回复: 这里你提到的时间复杂度具体是指？
2020-03-281- Being嗯，V是节点的数量，E是边的数量，根据邻接矩阵的概念来的。
作者回复: 思路是对的，不过V和E我们通常可以使用平均连接数来进一步推导，便于比较不同算法的好坏。具体的我会在第17讲的例子中讲解。
2019-01-201 
建强双向广度搜索算法的时间复杂度：取决于算法中的搜索次数，每次搜索之后，还要计算两个搜索结果的交集，而搜索次数是两个节点的共同好友交集中，到各自的出发点度数最大的那些节点。 空间复杂度：搜索过程中两者所有好友的结点数之和，即存贮已访问节点的存贮空间。作者回复: 是的
2020-03-01- 知行合一平均复杂度的计算稍微繁琐一些。如果距离为 n-1，只有 1 种可能，a 为数组中第一个字符，b 为数组中最后一个字符。如果距离为 n-2，那么 a 字符的位置有 2 种可能，b 在 a 位置确定的情况下只有 1 种可能，因此排列数是 2。以此类推，如果距离为 n-3，那么有 3 种可能，一直到距离 1，有 n-1 种可能。所以平均的扫描次数为 (1 *(n-1) + 2 *(n-2) + 3(n -3) + … + (n-1)1) / (1 + 2 + … + n)，最后时间复杂度简化为 O(n)。 老师，这个分母（1+2+•••+n）怎么理解
作者回复: 表示扫描的总次数
2019-12-11 
天佑看不懂里面的数学符号，怎么来的，为什么是log...作者回复: 你所说的log是指二分查找或归并排序的时间复杂度log(n)对吧。这里的log是以2为底，如果8个数字，那么就要查找3次，或者划分3次，也就是log(8)，以2为底
2019-07-03
罗耀龙@坐忘
茶艺师学编程 关于算法复杂度 1965年哈特马尼斯（Juris Hartmanis）和斯坦恩斯（Richard Stearns）提出了算法复杂度的概念（二人后来因此获得了图灵奖），而最早将复杂度严格量化衡量的是著名计算机科学家、算法分析之父高德纳（Don Knuth）。今天，全世界计算机领域都以高德纳的思想为准。 高德纳的思想主要有三部分： 1. 在比较算法的快慢时，需要考虑数据量特别特别大，大到近乎无穷大时的情况。 2. 决定算法快慢的因素虽然可能很多，但是所有的因素都可以被分为两类。第一类是不随数据量变化的因素，第二类是随着数量变化的。 3. 如果两种算法在量级上相当，在计算机科学里，就认为它们是一样好的。 大神的思想和今天老师讲的六原则，是不是已经很接近了?（特别是第三点） 回到思考题，请试着用使用规则，分析一下双向广度优先搜索的时间和空间复杂度。 （数学学渣，真的说错了请大家指教了） 由于是双头开始搜索，我猜其时间复杂度是O（logN），空间复杂度也应该是O(logN)2020-04-081
