大家好呀，我是蛋蛋。

数据结构与算法，作为编程界从入门到劝退的王者，是很多初学者心中神圣而想侵犯的村花儿，化身舔狗，费尽心思，舔到最后，我命油我不油天。

为了让臭宝们不再像我这样当个人这么难，我决定和大家一起学习数据结构与算法，我希望能用傻瓜的方式，由浅入深，从概念到实践，一步一步的来，这个过程可能会很长，我希望在这个过程中你能喜欢上它，能发现它们冰冷外表下有趣的灵魂。

---

复杂度分析

刚刚我说过，在本蛋看来，复杂度分析是数据结构和算法中最重要的知识点，毫不夸张的说，这就是数据结构与算法学习的核心所在。你学会了它你就入的了门，你学不会它，你就永远不知道门儿在哪。

为什么复杂度分析会这么重要/p>

这个就要从盘古开天辟地，呃，从数据结构与算法的本身说起。

臭宝：哇，厉害厉害厉害，你胖你说的都对，但还是没必要学啊。

蛋蛋：/p>

臭宝：现在有很多工具啊包啊，代码随便跑一下，就能轻轻松松知道运行了多少时间占了多少内存啊。算法的效率不就轻松比对出来了么/p>

蛋蛋：。。。

吐样吐森破！吃葡萄不吐葡萄皮！

你们说的这种主流叫做事后统计法。

简单来说，就是你需要提前写好算法代码和编好测试数据，然后在计算机上跑，通过最后得出的运行时间判断算法时效的高低，这里的运行时间就是我们日常的时间。

可以看出，我们需要一个不依赖于性能和规模等外力影响就可以估算算法效率、判断算法优劣的度量指标，而复杂度分析天生就是干这个的，这也是为什么我们要学习并必须学会复杂度分析！

时间复杂度

时间复杂度，也就是指算法的运行时间。

对于某一问题的不同解决算法，运行时间越短算法效率越高，相反，运行时间越长，算法效率越低。

那么如何估算时间复杂度呢/p>

大佬们在拽掉脑阔上最后一根头发的时候发现，当用运行时间去描述一个算法快慢的时候，算法中执行的总步数显得尤为重要。

因为只是估算，我们可以假设每一行代码的运行时间都为一个 Btime，那么算法的总的运行时间 = 运行的总代码行数。

下面我们来看这么一段简单的代码。

在上面假设的情况下，这段求累加和的代码总的运行时间是多少呢/p>

第 2 行代码需要 1 Btime 的运行时间，第 4 和 第 5行分别运行了 n 次，所以每个需要 n * Btime 的运行时间，所以总的运行时间就是 (1 + 2n) * Btime。

我们一般用 T 函数来表示****赋值语句的总运行时间，所以上面总的运行时间就可以表达成 T(n) = (1 + 2n) * Btime，翻译一下就是“数据集大小为 n，总步数为 (1 + 2n) 的算法的执行时间为 T(n)”。

通过公式，我们可以看出 T(n) 和总步数是成正比关系，这个规律的发现其实是很重要的，因为这个告诉了我们一种趋势，数据集规模和运行时间之间有趋势！

所有人准备，我们很熟悉的大 O 闪亮登场了！

n 作为数据集大小，它可以取 1，10，100，1000 或者更大更大更大的数，到这你就会发现一件很有意思的事儿，那就是当数据集越来越大时，你会发现代码中的某些部分“失效”了。

还是以之前的代码为例。当 n = 1000 时，1 + 2n = 2001，当 n = 10000 时，1 + 2n = 20001，当这个 n 持续增大时，常数 1 和系数 2 对于最后的结果越来越没存在感，即对趋势的变化影响不大。

所以对于我们这段代码样例，最终的 T(n) = O(n)。

接下来再用两段代码进一步学一下求时间复杂度分析。

时间复杂度分析

代码 1

这段代码我会从最开始一点点带你来。

第 2 行需要运行 1 次 ，第 4 行需要运行 n 次，第 5 行和第 6 行分别需要运行 n2 次。所以总的运行次数 f(n) = 1 + n + 2n2。

当 n 为 5 的时候，f(n) = 1 + 5 + 2 * 25，当 n 为 10000 的时候，f(n) = 1 + 10000 + 2 * 100000000，当 n 更大呢/p>

这个时候其实很明显的就可以看出来 n2 起到了决定性的作用，像常数 1，一阶 n 和 系数 2 对最终的结果（即趋势）影响不大，所以我们可以把它们直接忽略掉，所以执行的总步数就可以看成是“主导”结果的那个，也就是 f(n) = n2。

自然代码的运行时间 T(n) = O(f(n)) = O(n2)。

代码 2

上面这段代码是求三部分的和，经过之前的学习应该很容易知道，第一部分的时间复杂度是 O(n)，第二部分的时间复杂度是 O(n2)，第三部分是 O(n3)。

正常来讲，这段代码的 T(n) = O(n) + O(n2) + O(n3)，按照我们取“主导”部分，显然前面两个小弟都应该直接 pass，最终 T(n) = O(n3)。

通过这几个例子，聪明的小婊贝们肯定会发现，对于时间复杂度分析来说，只要找起“主导”作用的部分代码即可，这个主导就是最高的那个复杂度，也就是执行次数最多的那部分 n 的量级。

剩下的就是多加练习，有意识的多去想多去练，就可以和我一样 帅气 稳啦。

假设需要 x 个，那么相当于求：

所以上述代码的时间复杂度应该为 O(log2n)。

但是对于对数复杂度来说，不管你是以 2、3 为底，还是以 10 为底，通通记作 O(logn)，这是为什么呢/p>

这就要从对数的换底公式说起。

对于时间复杂度来说：

最好情况、最坏情况和平均情况时间复杂度

除了数据集规模影响算法的运行时间外，“数据的具体情况”也会影响到运行时间。

我们来看这么一段代码：

上面这段简单代码是求变量 word 在列表 lst 中出现的位置，我用这段来解释“数据的具体情况”是什么意思。

变量 word 可能出现在列表 lst 的任意位置，假设 a = [‘a’, ‘b’, ‘c’, ‘d’]：

• 当 word = ‘a’ 时，正好是列表 lst 的第 1 个，后面的不需要再遍历，那么本情况下的时间复杂度是 O(1)。
• 当 word = ‘d’ 或者 word = ‘e’ 时，这两种情况是整个列表全部遍历完，那么这些情况下的时间复杂度是 O(n)。

这就是数据的具体情况不同，代码的时间复杂度不同。

根据不同情况，我们有了最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度这 3 个概念。

最好情况时间复杂度

最好情况就是在最理想的情况下，代码的时间复杂度。对应上例变量 word 正好是列表 lst 的第 1 个，这个时候对应的时间复杂度 O(1) 就是这段代码的最好情况时间复杂度。

最坏情况时间复杂度

最坏情况就是在最差的情况下，代码的时间复杂度。对应上例变量 word 正好是列表 lst 的最后一个，或者 word 不存在于列表 lst，这个时候对应的时间复杂度 O(n) 是这段代码的最坏情况时间复杂度。

平均情况时间复杂度

大多数情况下，代码的执行情况都是介于最好情况和最坏情况之间，所以又出现了平均情况时间复杂度。

那怎么计算平均时间复杂度呢个说起来有点复杂，需要用到概率论的知识。

在这里我还是用上面的例子来讲，因为只是简单的科普一下，为了方便计算，我假设的会有点随意：

• 从大的方面来看，查找变量 x 在列表 lst 中的位置有两种情况：在或者不在。假设变量 x 在或者不在列表 lst 中的概率都为 1/2。
• 如果 x 在列表 lst 中，那么 x 有 n 种情况，它可能出现在 0 到 n-1 中任意位置，假设出现在每个位置的概率都相同，都为 1/n。

每个出现的概率（即权重）知道了，所以平均时间复杂度为：

臭宝：又是最好，又是最坏，又是平均的，这么多到底用哪个呀/p>

蛋蛋：这个还用问然是选择最坏情况时间复杂度啊！

最好情况，反应最理想的情况，怎么可能天上天天掉馅饼，没啥参考价值。

平均情况，这倒是能反映算法的全面情况，但是一般“全面”，就和什么都没说一样，也没啥参考价值。

最坏情况，干啥事情都要考虑最坏的结果，因为最坏的结果提供了一种保障，触底的保障，保障代码的运行时间这个就是最差的，不会有比它还差的。

所以，不需要纠结各种情况，算时间复杂度就算最坏的那个时间复杂度即可。

空间复杂度

空间复杂度相较于时间复杂度来说，比较简单，需要掌握的内容不多。

空间复杂度和时间复杂度一样，反映的也是一种趋势，只不过这种趋势是代码运行过程中临时变量占用的内存空间。

臭宝：为什么是“临时”咧/p>

蛋蛋：这就要从代码在计算机中的运行说起啦。

代码在计算机中的运行所占用的存储空间呐，主要分为 3 部分：

• 代码本身所占用的
• 输入数据所占用的
• 临时变量所占用的

前面两个部分是本身就要占这些空间，与代码的性能无关，所以我们在衡量代码的空间复杂度的时候，只关心运行过程中临时占用的内存空间。

空间复杂度记作 S(n)，表示形式与时间复杂度一致。

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33897 人正在系统学习中

来源：编程文青李狗蛋