算法的时间复杂度和空间复杂度详解
想象一下两个功能完全相同的程序。如果分别输入一千条记录，你根本分辨不出它们的区别。但如果输入十亿条记录，一个程序在你松开回车键之前就已经完成了，而另一个程序可能要到下周二还在运行。
同一台笔记本电脑，相同的数据。它们之间的区别在于时间复杂度，时间复杂度指的是随着输入数据的增加，算法工作负载增长的速度。
我们将深入探讨这个术语的真正含义，大O符号如何表示它，如何从实际代码中计算出它的复杂度，以及空间复杂度是如何体现的。最后，我们将讨论一个真正能将这一切从理论知识应用到实际商业决策中的地方：智能合约。
算法的时间复杂度是什么？
暂时忽略秒数。时间复杂度计算的是步骤数。比较、赋值、零星的算术运算，最终将总时间复杂度表示为输入规模 n 的函数。
这是你能想象到的最无聊的功能：
python def print_all(items): for item in items: print(item)
十件物品？绕圈十次。一万件物品？绕圈一万次。
计算量沿着输入旁边的直线上升，因此我们称之为 O(n)。
现在，也许每次行程实际上需要三次小操作而不是一次。好吧，那就是 3n。说实话，没人会在意，因为清单翻倍工作量也翻倍，而我们想要的正是这种增长曲线。确切的数字我们故意忽略了。
这也是为什么所有数据结构与算法课程以及一半的编程面试都会重点考察时间复杂度的原因。如果你能通过观察算法本身来判断其复杂度，你就能预测它在那些你从未测试过的输入数据上的表现。而在实际生产环境中，这些数据几乎占了绝大多数。
为什么执行时间并非衡量算法性能的可靠指标
那么为什么不直接用定时器运行呢？很多人都这么做，我能理解。但问题在于，执行时间会牵扯到一大堆与你的算法无关的东西：
- 硬件方面，我用了五年的笔记本电脑和一台全新的云服务器运行同一个脚本，结果会截然不同。
- 编程语言。用 C 语言和 Python 编写相同的循环，你可能会发现结果相差 10 倍甚至更多。
- 系统负载过高。后台更新程序启动，垃圾回收器开始工作，缓存冷却。结果会发生变化。
- 无论你获取的输入是什么。一种在接近有序的数据上速度极快的排序算法，在打乱的数据上速度可能很慢。
秒表只能记录一次在一个设备上输入一个数据后的运行情况。如果要求它记录 100 倍的数据，它就什么也记录不了。
步骤数不会波动。同样的算法，同样的输入，无论是在机架服务器上用 Rust 运行，还是在某人的手机上用 JavaScript 运行，得到的步骤数都相同。这就是为什么在进行基准测试之前，两种解决方案在时间复杂度上的比较是公平的。当然，即便如此，我仍然建议之后进行基准测试。这只是另一个问题而已。
大O符号和其他渐近符号的解释
教科书称之为渐近符号，听起来比实际情况要复杂得多。你让 n 变得非常大，不再关注那些细小的因素，因此常数乘数和微小的输入都会消失，只剩下增长曲线。其中有三个值得了解：
| 符号 | 它描述的是什么 | 字面意思 | 例子 |
|---|---|---|---|
| 大O，O(f(n)) | 上限 | 该算法的增长速度不会超过 f(n)。 | 线性搜索的时间复杂度为 O(n) |
| 大Ω，Ω(f(n)) | 下限 | 该算法至少需要 f(n) 个工作量 | 任何比较排序都是 Ω(n log n) |
| Big-Theta，Θ(f(n)) | 紧绷的 | 上下限匹配 | 归并排序的时间复杂度为Θ(n log n) |
在实践中，你大约 95% 的情况下都会听到大 O 表示法。它设定了一个上限，意味着运行时间的增长速度不会超过括号内的速度。我在正式工作中第一次进行代码审查时，一位高级开发人员在一个嵌套循环旁边写道“O(n²)，请修复”，他的意思是说最坏情况下的时间复杂度是二次方的，而且列表很快就会变得非常长。
Omega 和 Theta 主要存在于大学算法分析课程中，我想我已经好几年没在工作中用到它们了。大 O 表示法之所以胜出，是因为它回答了人们在会议上实际提出的问题，即“如果流量增加三倍，情况会变得多糟糕？”
有一个技术细节让我困惑了一段时间。由于大O符号只是一个上限，严格来说，O(n)函数也等于O(n²)，就像身高5英尺的人“不到7英尺”一样。这说法没错，但没什么实际意义。大家都会引用他们能找到的最紧的界限，我也会这么做。
常见时间复杂度类及其示例
实际代码中你不会看到那么多类，如果算上那些比较复杂的类，可能也就七个。以下是 n = 1000 时每个类的大致成本：
| 班级 | 姓名 | 典型示例 | n = 1,000 时的运算 |
|---|---|---|---|
| O(1) | 持续的 | 数组索引，哈希表查找 | 1 |
| O(log n) | 对数 | 二分查找 | 约10 |
| 在） | 线性 | 扫描列表 | 1,000 |
| O(n log n) | 线性对数 | 归并排序，快速排序（平均） | 约10,000 |
| O(n²) | 二次方程 | 嵌套循环，冒泡排序 | 1,000,000 |
| O(2ⁿ) | 指数 | 朴素递归斐波那契数列 | 宇宙中的数量远超原子数量。 |
| 在！） | 阶乘 | 蛮力型旅行推销员 | 甚至更大 |
O(1): 常数时间
无论你的 Python 字典有十个键还是一千万个键，按键提取一个键的成本都差不多，从列表中读取项也是如此[5]。这种扁平性正是常数时间的关键所在。
O(log n)：对数时间
我把这些算法看作是“猜1到100之间的数字”的算法，其中每次猜测都会排除剩余选项的一半。二分查找在已排序列表中正是如此运作的：
Python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
对于十亿个已排序的项目，大约需要进行 30 次比较，而如果一个一个地进行比较，则可能需要整整十亿次比较，我一直觉得这很滑稽。
O(n) 和 O(n log n)
线性算法会遍历每个元素固定次数，就像你用肉眼在电子表格列中寻找最大值一样。O(n log n) 是优秀排序算法的基础。归并排序会将列表拆分成单个元素（拆分为 log n 层），然后在合并过程中对每一层元素进行一次线性遍历，因此无论数据是有序的还是乱序的，其运行时间都保持不变。
O(n²) 及更差
二次码几乎总是包含一个嵌套循环，例如这个重复项检查，它会比较每一对数据：
Python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
指数增长和阶乘增长的情况要糟糕得多。教科书上的递归斐波那契数列不断地重复求解相同的子问题，因此 n 每增加 1，工作量就会大致翻倍。当 n = 20 时，你可能感觉不到；但当 n = 60 时，即使你做好晚饭、吃完饭、洗完碗，计算也还没完成。
如何逐步计算时间复杂度
你几乎不需要正式的证明就能计算时间复杂度。我会在脑子里快速过一遍以下列表，它涵盖了我见过的绝大多数代码：
- 定义 n。确定输入的大小：列表的长度、图中的节点数、数字的位数。
- 计算每一行的工作量。简单的语句（赋值、比较、算术）的成本为 O(1)。
- 添加连续的块。两个循环依次遍历 n，得到 n + n = 2n。
- 将嵌套块相乘。在一个遍历 n 的循环中嵌套另一个遍历 n 的循环，得到 n × n = n²。
- 去掉常数。2n变为 n，500 变为 1。
- 只保留主导项。在 n² + n 中，随着 n 增大，n² 部分远大于其他部分。
快速计算一下。你的计算结果是 T(n) = 3n² + 5n + 2。加上一百万：3n² 是三万亿，5n 是五百万。四舍五入误差。记为 O(n²)，搞定。
循环语句如果跳过某些步骤而不是逐个执行，则更加隐蔽：
Python 函数 `count_halvings(n)` 定义如下：`steps = 0`，当 n > 1 时，`n` 的值变为 2，`steps += 1`，然后返回 `steps`。
每次迭代都会将 n 减半，因此这个 while 循环大约会在 log₂(n) 轮后停止。这基本上就是“时间复杂度何时为 O(log n)？”这个问题的全部答案。如果每次迭代剩余的 n 值都按常数因子缩小，那么就达到了 O(log n) 的条件。
递归需要另一个工具，即递归式。归并排序执行两个半大小的任务，然后进行合并，因此 T(n) = 2T(n/2) + n。主定理是这种形状递归式的速查表，对于这种情况，它给出的结果是 O(n log n)。
我经常参考算法竞赛中的一个经验法则：一台普通的机器每秒大约可以完成 10⁸ 次简单操作。这只是一个粗略的估计，但足以在提交之前检查解决方案的时间复杂度。当 n 为 10⁵ 时，O(n²) 大约需要 10¹⁰ 次操作，因此会超时。而 O(n log n) 则不到 200 万次操作，可以轻松通过。
最坏情况、最佳情况和平均情况分析
给同一个算法输入不同的数据，计算量可能会出现巨大波动。线性搜索很好地说明了这一点：
- 最佳情况：你想要的东西就在最前面。只需比较一次，就能排除掉它。
- 最糟糕的情况：它要么排在最后，要么根本不存在。这需要进行 n 次比较。
- 平均而言：如果任何位置出现的概率都相等，那么平均需要检查大约 n/2 次。但时间复杂度仍然是 O(n)。
如果你问开发人员某件事的“复杂性”，他们几乎总是会告诉你最坏情况下的时间复杂度，因为这个数字是一个你可以据此进行规划的承诺。
假设你的 API 处理请求的最坏情况复杂度为 O(n)。很好，现在你知道最慢的请求会如何表现，而且当有人故意发送垃圾数据时，你也能应对自如。确实有人会这么做：如果攻击者找出哪些键会导致你的哈希表冲突，那么在一段时间内，你只会看到这些键。
平均情况值得关注，因为最糟糕的情况几乎不会出现。快速排序就是个典型例子，它的平均时间复杂度为 O(n log n)，但如果对已经排序的数据随意选择枢轴点，时间复杂度就会滑落到 O(n²)。标准库通过随机选择枢轴点来解决这个问题，或者在递归深度过深时切换到其他排序算法。
什么是空间复杂性和辅助空间？
内存是算法运行过程中消耗的另一项资源。空间复杂度衡量的是随着输入规模的增长，你需要多少空间，它和时间复杂度一样，都使用大O符号来表示。
这部分内存的一部分是输入数据本身，无论你如何处理它，都需要为此付费。你真正能控制的部分叫做辅助空间，指的是代码运行过程中分配的额外空间，例如临时变量和新数组，以及调用栈——通常只有在出现问题时才会被人注意到。
几个简单的例子：
- 交换两个变量需要占用几个槽位，这是不考虑其他因素的，因此辅助空间为 O(1)。
- 将包含 n 个元素的列表复制到一个新列表中需要 O(n) 的额外内存。
- 递归 n 层深度会在栈上留下 n 个帧，即使你从未构建过数组，空间复杂度也为 O(n)。
我亲眼看到一个初级开发人员为了解决最后一个问题浪费了一个下午。他们的递归函数看起来完全没有占用内存，但每个未完成的调用都堆积在栈上，等待更深层的调用返回结果，结果在处理大型输入时，整个程序因为栈溢出而崩溃。
许多优化其实就是内存和时间之间的权衡。记忆化会缓存已经计算过的结果，这使得简单的斐波那契数列计算从 O(2ⁿ) 的时间复杂度降低到 O(n)，但代价是占用 O(n) 的内存。哈希表通过在存储桶上分配空间，将平均查找时间复杂度降低到 O(1)。在拥有 64 GB 内存的服务器上，这种权衡通常是显而易见的，但在微控制器或智能合约中，你就需要仔细考虑了。
常见数据结构的时空复杂度
选择合适的数据结构通常比对循环内部代码进行微调更重要。以下是几种最常用数据结构的平均成本：
| 数据结构 | 使用权 | 搜索 | 插入 | 删除 | 空间 |
|---|---|---|---|---|---|
| 大批 | O(1) | 在） | 在） | 在） | 在） |
| 链表 | 在） | 在） | O(1) | O(1) | 在） |
| 哈希表 | 不适用 | O(1) | O(1) | O(1) | 在） |
| 平衡二叉搜索树 | O(log n) | O(log n) | O(log n) | O(log n) | 在） |
| 二叉堆 | O(1) 表示最小值/最大值 | 在） | O(log n) | O(log n) | 在） |
两个脚注。链表的插入和删除操作只有在节点已存在的情况下才是 O(1)。而哈希表在键冲突较多时，时间复杂度可能会达到 O(n)。
排序算法的种类也同样繁多：
| 排序算法 | 最好的 | 平均的 | 最差 | 辅助空间 |
|---|---|---|---|---|
| 冒泡排序 | 在） | O(n²) | O(n²) | O(1) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | 在） |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) |
归并排序结果可预测，但需要额外的内存。堆排序进行原地排序，最坏情况下的性能也相同。快速排序虽然性能上限较低，但在实践中往往更胜一筹。
区块链和智能合约的时间复杂度
有趣的地方来了。在你自己服务器上，糟糕的算法会浪费 CPU 资源，或许还会惹恼用户。但在以太坊或其他任何 EVM 链上，它会浪费金钱。智能合约执行的每个操作码都需要消耗 gas，gas 以链上的原生代币支付，因此你的操作次数会体现在别人的账单上。换句话说，糟糕的时间复杂度是要付出代价的。
假设你有一个合约，它会遍历所有代币持有者来支付奖励。时间复杂度为 O(n)，并且每增加一个持有者，gas 费用就会增加。在上线当天，没有人会注意到这一点。
然后持有者列表不断增长。有一天，支付所需的 gas 量超过了区块 gas 上限（即单个区块可以容纳的 gas 量上限）。之后，交易就无法完成。不是“速度慢”，而是根本无法成功，所有等待处理该函数的资金基本上都被困住了。审计人员会将这种无限循环的事件归类为拒绝服务攻击，这无可厚非。
这些解决方法本质上就是复杂性思维：
- 将工作分成固定大小的批次，分多次交易完成。
- 反过来，每个用户都可以领取自己的奖励。每次调用的时间复杂度为 O(1)。
- 将循环替换为默克尔证明。
我喜欢用默克尔证明来举例说明为什么链上对数 n 如此重要。默克尔树将大量数据哈希到一个根哈希值。
要证明一个条目属于包含 n 个条目的集合，大约需要 log₂(n) 个哈希值。对于一百万个条目来说，这大约是 20 个哈希值，而不是一百万个。空投正是利用了这一点，轻量级比特币钱包也使用同样的技巧来确认交易，而无需下载整个区块。
链下支付也是如此。想象一下，一个支付后端需要扫描每张未结发票，才能将每笔传入的区块链交易与对应的发票进行匹配。每次支付的时间复杂度为 O(n)，而且随着店铺规模的扩大，速度会越来越慢。如果将发票放入以地址或 ID 为键的哈希映射表中，每次匹配的时间复杂度就降至 O(1)。如果您不想自己构建和维护这些底层架构，可以使用像Plisio这样的加密支付网关来代劳。
