逃不开的时空复杂度：理解大O记号才算入门算法

算法第一课为什么逃不开时空复杂度如果你刚开始刷算法题或者准备系统地补数据结构十有八九会遇到这个开头。不管你看的是哪份教程目录里总会有一个“0.”后面跟着四个字时空复杂度。很多人在这一节就卡住了觉得又是数学符号又是函数曲线还没走到排序和二分查找就先熄火了。我个人的态度很直接复杂度分析不是算法里最难的部分但它是最值得先花半天搞明白的部分。因为后面所有数据结构和算法的取舍本质都在回答同一个问题——这个方案在数据量变大时时间和空间会怎样变化。搞懂复杂度你就有了一把尺子搞不懂你看任何题解都只能背结论换个数就不再理解了。这篇文章我打算用比较实在的讲法把时间复杂度和空间复杂度掰开揉碎。不堆数学证明尽量用代码、例子和实际场景让你建立直觉再穿插一些我实际分析代码时踩过的坑希望能帮你少走点弯路。1. 为什么学算法要先学复杂度从“跑得太慢”说起1.1 实测时间为什么不能当作评判标准最开始我也干过这种事写完两个算法分别跑一遍看哪个用时更短。比如对比冒泡排序和快速排序拿一个只有几十个元素的数组去测结果极其迷惑——有时候冒泡还更快。因为初始化那几毫秒、系统调度、CPU 缓存状态都在影响结果你测的根本不是算法的能力而是当前机器那一瞬间的心情。但如果把数组规模从几十涨到几万、几十万差距就出来了。冒泡排序开始以肉眼可见的速度变慢快速排序依然从容。问题在于你不能每次都靠“实际跑一把”来比较算法因为你没法穷举所有输入规模也没法保证两台机器的环境一致。这就需要一个脱离具体机器的度量方式。1.2 复杂度衡量的是“增长趋势”而不是“时间秒数”时间复杂度的本质是算法执行时间随输入规模 n 增长时的变化趋势。我们不关心 n100 的时候用了 0.1 毫秒还是 0.2 毫秒我们关心的是 n 翻倍、变成 1000 倍、变成 1000000 倍的时候执行时间大概会变成多少倍。这有点像评估一个交通方案不是看你今天出门开到公司花了 20 分钟还是 30 分钟而是看路上车流量涨 10 倍以后你还能不能在一个小时内到。有些方案在流量小的时候非常快车一多就全线堵死有些方案起步慢但路况再差也只是线性地变慢。算法的复杂度分析就是在交通规划阶段评估这种“抗压能力”。空间复杂度同理度量的是算法运行过程中额外内存随输入规模的增长趋势。两者合在一起就是“时空复杂度”这个词的含义。2. 大O记号面向增长率的数学速记2.1 大O到底在说什么大O记号是复杂度分析的通用语言。它回答的是一个上界问题当 n 足够大的时候算法的操作次数不会超过某个数量级。注意是“不会超过”也就是说它关心的是最坏情况下的增长上限。我见过不少初学者纠结大O的精确定义甚至被 epsilon-delta 语言吓退。实际上你不需要那么严谨——你用“忽略常数系数、忽略低阶项、只保留下最高阶项”这三条规则去理解就够了。比如一个算法总共执行 (3n^2 5n 8) 次操作。n10 的时候这三项分别是 300、50、8低阶项还挺有存在感但 n10000 的时候第一项是 300000000后两项加起来才 50008可以忽略不计。所以这个算法的时间复杂度就是 (O(n^2))。2.2 常见复杂度量级横评我把平时最常碰到的几个量级放在一起对比方便你有个体感量级名称体感类比100个元素的操作次数参考O(1)常数时间直接翻到书签那一页1O(log n)对数时间电话簿里二分查找人名约7O(n)线性时间一页页翻书找内容100O(n log n)线性对数时间把一堆文件按姓名排序约700O(n^2)平方时间两层循环暴力查重10000O(2^n)指数时间枚举所有子集2的100次方人类无法想象这里有个特别容易误判的点很多人看到 O(log n) 觉得“这不就是一条往下走的曲线嘛应该很小”但不少排序算法的下限就是 O(n log n)比 O(n) 大。对数的底数是多少不重要因为换底公式只差一个常数重要的是它增长得极其缓慢哪怕是 n 等于 10 亿级别log n 也就三十几。2.3 为什么可以忽略常数项和低阶项有人会质疑真实工程里常数项差别可能非常大啊。同样是 O(n)一次循环和十次循环系数差了十倍难道没影响吗有影响但这不是复杂度分析要解决的问题。复杂度的价值在于判断“随着 n 变大谁先撑不住”。当 n 足够大时一个常数系数大但复杂度低的算法会反杀一个常数系数小但复杂度高的算法。比如 (100n) 和 (n^2)n10 时前者还更大但 n200 时 100n 是 20000n^2 是 40000已经追上了到 n1000差距就是 10 万对 100 万。所以复杂度分析适合做“跨量级判断”O(n) 和 O(log n) 有本质差别O(n) 和 O(2n) 没有本质差别。把常数级别的优化留给实际 profiling 去做。3. 时间复杂度的手撕过程从代码到函数3.1 顺序结构关键看循环而不是总行数分析一段代码的时间复杂度不需要一行行数执行行数也不需要管声明变量的开销。核心是找那些会重复执行的结构尤其是循环和递归。判断循环的本质是搞清楚循环变量从哪开始、到哪结束、每次怎么变化。最基础的三类# 情况一固定次数循环n次 def example1(n): total 0 for i in range(n): total i return total# 情况二循环次数随i减半每次i翻倍 def example2(n): i 1 count 0 while i n: i * 2 count 1 return count# 情况三循环次数和输入规模无关永远100次 def example3(n): total 0 for i in range(100): total n return total情况一是典型的 O(n)很好判断。情况二的执行次数是 log₂n 的量级因为 i 从 1 出发乘以 2 到超过 n一共执行了约 log₂n 次——这是 O(log n) 最常见的来源而它只出现在“规模每次折半/翻倍”的场景里。情况三看起来很吓人但循环固定 100 次和 n 没有任何关系所以是 O(1)。3.2 循环嵌套相乘而不是相加分析嵌套循环时有个口诀外层循环复杂度 × 内层循环复杂度。但注意这个“相乘”不是无脑套公式你得先确认每一层循环的变化范围。最经典的双层循环def nested_example(n): for i in range(n): for j in range(n): print(i, j)外层执行 n 次每次内层都执行 n 次总操作量是 n × n n²所以是 O(n^2)。另一种很常见的“优化版”双层循环def half_nested_example(n): for i in range(n): for j in range(i, n): print(i, j)内层循环从 i 到 n总执行次数是 (n (n-1) (n-2) ... 1 n(n1)/2)约等于 0.5n²。按规则去掉常数系数后依然是 O(n^2)。这就是为什么很多题解里所谓的“剪枝一半”不会改变复杂度量级——它只优化了常数没有改变增长趋势。还有一种容易踩坑的嵌套内外层都用同一个变量缩影。def tricky_nested_example(n): i 1 while i n: j i while j n: j * 2 i 1外层是 O(n)内层每次从 i 到 n 翻倍是 O(log n)。所以整体是 O(n log n)。计算过程虽然不复杂但你必须仔细看每一层的迭代步长而不是只数一下有没有两层循环就草率定结论。3.3 递归时间复杂度的直观拆解递归的时间复杂度比循环难判断因为循环是显式的重复递归是隐式的重复。最简单也最实用的方法是写出递推关系然后展开观察规律。注意我不打算讲严格的主定理先用最直观的“二叉树展开”来看。拿最常见的二分查找举例def binary_search(nums, target, left, right): if left right: return -1 mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: return binary_search(nums, target, mid 1, right) else: return binary_search(nums, target, left, mid - 1)每次递归调用只会走一个分支问题规模减半。递归层数约 log n每层只做 O(1) 操作所以时间复杂度 O(log n)。再看一个容易吓倒人的例子——朴素递归斐波那契def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)它的递归树大致是一棵二叉树的形状每个节点分裂出两个子节点树的深度约等于 n节点总数约等于 (2^n) 级别。所以朴素递归版的时间复杂度是指数级的 O(2^n)n 到 50 就已经慢到无法接受。这就是为什么面试里提到斐波那契基本不可能让你写朴素的递归版本而是会引导你用带备忘的递归或者动态规划。3.4 分析工具把循环次数统计出来很多时候你不需要精确统计代码执行了多少步但你至少要会“算账”。我的习惯是先数“核心操作重复执行的次数”再写成一个关于 n 的式子最后化简成大O。举一个我实际在代码评审里遇到过的例子“查找数组中的多数元素出现次数超过一半”。最简单的暴力法是两层循环每层都遍历整个数组这明显是 O(n^2)。后来用哈希表统计出现次数遍历两次数组每次 O(n)总共 O(n)。再往后用摩尔投票法只遍历一次常数空间依然是 O(n)。同样是 O(n)后者的空间从 O(n) 降成了 O(1)。这就说明复杂度只告诉你增长趋势一样不告诉你系数和空间细节真正落地时还得看额外条件。4. 空间复杂度除了O(1)还有什么4.1 空间复杂度的计数口径空间复杂度看的是除了输入本身占用的内存之外算法在运行过程中额外开辟的存储空间大小。注意两个容易被忽视的细节第一输入数据本身不算。你处理一个长度为 n 的数组数组本身已经存在了这不叫额外空间讨论的是你创建的辅助数据结构、递归调用栈、临时变量等。第二变量的个数单独数没有意义要看它随 n 怎么变化。比如一个临时变量存中间结果不管 n 多大都只有一个这是 O(1)但如果 new 一个长度为 n 的辅助数组这就是 O(n)。4.2 同一个功能两种空间写法的对比拿“原地反转数组”来举例这是最能说明空间复杂度差异的场景。第一种新建一个数组从后往前填进去。def reverse_array_copy(arr): n len(arr) new_arr [0] * n for i in range(n): new_arr[i] arr[n - 1 - i] return new_arr这里的辅助数组长度是 n所以额外空间是 O(n)。时间上是单层循环O(n)。第二种原地双指针交换。def reverse_array_inplace(arr): left, right 0, len(arr) - 1 while left right: arr[left], arr[right] arr[right], arr[left] left 1 right - 1只有两个指针变量没有随 n 增长的额外空间额外的空间就是 O(1)。功能一模一样但空间从 O(n) 降到 O(1)。这是面试里最常见的追问“能不能空间换时间”、“能不能原地操作”4.3 递归调用栈也是一种空间很多初学者算递归的空间复杂度容易忽略一件事每一次递归调用会在系统的调用栈上压一层栈帧栈帧里保存了局部变量和返回地址。递归深度是多少空间开销就是多少。比如上面那个二分查找递归深度 O(log n)空间复杂度就是 O(log n)——哪怕代码里没有显式创建任何数组调用栈本身就是空间占用。再比如递归斐波那契递归深度达到 n空间复杂度是 O(n)注意这跟它的时间 O(2^n) 不是一回事。这带来一个很实际的影响当递归深度过深时即使时间复杂度看着不高也可能因为调用栈爆掉而直接崩溃。我之前处理过一个数据量并不大的多叉树遍历因为树深度不理想递归版本在极端数据下居然栈溢出了后来改成显式栈迭代才解决问题。空间复杂度的意义有时不只在“省内存”还在于“稳得住”。5. 复杂度分析的常见误判与实战建议5.1 误判一看到遍历就默认O(n)不是所有遍历都是 O(n)。如果遍历过程中跳过了很多元素或者每个元素只处理了一次仍然是 O(n)但如果遍历步长是指数增长的就可能变成 O(log n)。更隐蔽的是那种看似线性的“双指针”遍历如果左右指针分别扫每个指针最多移动 n 步总体还是 O(n)不是 O(n²)——两个指针不是嵌套关系是顺序关系。我见过有人写滑动窗口的题内外看起来像两层循环直接判断 O(n²)结果被面试官追问“你确定吗”实际上滑动窗口里的 left 和 right 各自最多移动 n 次内部虽然用了 while但总体执行次数是 2n 级别复杂度是 O(n)。分析这种代码时要算的是所有指针移动总次数而不是简单地“有循环嵌套就是 O(n²)”。5.2 误判二忽略API调用的隐藏复杂度最容易被坑的地方往往不是你自己写的循环而是别人封装好的函数。很多人写代码时数了层数却没注意到某一行调用了标准库方法这一行背后可能藏着一个 O(n) 甚至 O(n²) 的操作。随手举个例子def remove_first_elements_bad(lst, k): for _ in range(k): lst.pop(0) return lst在 Python 里list.pop(0) 会把后面所有元素往前挪一位复杂度是 O(n)。外层再循环 k 次整体就是 O(kn) 量级。如果 k 接近 n那就是 O(n²)。换成 deque.popleft() 或者直接截断切片就能把它降下来。再比如字符串拼接在循环里用 逐字符拼接每次拼接都可能触发一次字符串拷贝循环 n 次就是 O(n²)。改用 list 收集再 “”.join()一次性生成结果就能回到 O(n)。这类问题不是靠“背复杂度”能避免的只能靠你对自己用的语言的数据结构实现有基本了解。5.3 误判三递归深度和时间复杂度混淆有人看到递归就写 O(2^n)看到迭代就觉得是 O(n)这也不对。比如二分查找的递归版是 O(log n)它的迭代版也是 O(log n)差的只有空间上的调用栈。决定时间复杂度的不是“递归还是迭代”这个形态而是“每层递归分裂出多少子问题、合并子问题的成本是多少、递归树有多深”。判断递归复杂度的通用思路是画递归树每个节点代表一次函数调用树的高度由递归深度决定节点总数大致就是调用总次数每层/每次调用的 O(1) 操作再叠加如果画完递归树仍然不确定就找递推式展开。二分查找对应 (T(n) T(n/2) O(1))归并排序对应 (T(n) 2T(n/2) O(n))。后者每层合并要扫一遍子区间整棵树有 log n 层每层总工作量 O(n)所以总复杂度是 O(n log n)。这套“树高 × 每层工作量”的思考路径比死记主定理实用得多。5.4 只有一份代码时怎么快速估算如果没有现成的题解可以参考我给你一个我自己常用的“三步估算”法第一步找到主轴代码路径。也就是去掉上下文的初始化、清理、异常处理这部分找到算法主体中会反复执行的代码片段。第二步为每个代码路径标注循环变量变化方式。具体说就是循环跑几次每次迭代步长是 1、2、倍增还是减半内层和外层的变量之间有没有依赖第三步把结果写成关于 n 的式子。先留常数最后统一去掉低阶和系数只保留最高阶量级。这个方法不能保证你得到最精确的复杂度但足够应对绝大多数算法题和代码评审场景。你要是真的遇到特别复杂的递归或嵌套结构再用递推式或者递归树做深度分析而不是一上来就在脑子里硬背答案。我自己的体会是复杂度分析这门功夫是越用越熟的。前面几次分析可能慢、可能错但只要你把每个题解里的复杂度部分拆开重新算一遍坚持十几道题之后看到一段代码就能迅速脑内算出量级。到那时候你去选数据结构、选算法策略都会比单纯“记住结论”的人快得多。