第一次被“时间复杂度”“空间复杂度”这两个概念劝退的人绝对不止你一个。我当年刚碰数据结构与算法时看到代码旁边标着 O(n)、O(n²)第一反应是这到底是什么神奇符号后来才慢慢想明白它其实在回答两个非常实际的问题程序面对更大规模的数据时到底会变慢多少又会占掉多少内存不管你是准备面试、刷题还是想优化线上接口这两个概念都绕不开。这篇东西我想用自己的理解把这件事彻底讲透顺便分享一些平常不太容易从教科书里看到的坑。1. 先说清楚时间复杂度和空间复杂度到底在算什么1.1 时间复杂度不要盯着秒表要看增长趋势很多人刚学的时候有个误区以为时间复杂度是“运行时间”。严格说它描述的是算法执行时间随输入规模增长的变化趋势不是某一台机器上跑出来的毫秒数。举个例子。你在一家快递站点分拣包裹包裹数量从 100 个变成 1000 个如果你每来一个包裹都要把所有已经分好的包裹重新翻一遍那工作量大概会变成原来的 10 倍甚至更多另一种方式是你按编号把包裹放到固定区域包裹变多你只是多走几步路。前者是 O(n²) 的感觉后者是 O(n) 的感觉。你说测量“每单耗时”有用吗有用但机器配置、CPU 频率、缓存命中率都会影响真正能跨设备比较的是这个趋势。正式一点说假设输入规模为 n算法基本操作次数是 f(n)。如果存在正常数 c 和 n₀当 n ≥ n₀ 时总有 f(n) ≤ c·g(n)我们就说时间复杂度是 O(g(n))。你不用被这个数学定义吓到它只是想表达一件事当 n 足够大以后f(n) 的增长速度不会超过 g(n) 的某个倍数。所以时间复杂度分析的核心是“找主项”循环跑几遍、递归展开多少层、每层又做了多少事把这些加起来去掉常数留下最高阶就是结果。比如某段代码总共执行 3n 5 次操作O(3n5) 和 O(n) 在复杂度级别上没区别因为常数系数不会改变增长走势。1.2 空间复杂度除了变量还有栈和临时数据空间复杂度度量的不是“代码文件占多少硬盘”而是算法运行过程中需要的额外内存随输入规模怎么变化。它同样用大 O 表示比如 O(1) 表示不管 n 多大额外内存基本固定O(n) 表示需要为 n 个元素分配对应的存储。新手最容易忽略的是空间复杂度不只看“你显式声明的数组和哈希表”还要看递归调用栈。你写一个递归函数每递归一层系统就要压一个栈帧保存参数、局部变量和返回地址。即便函数体里没有任何大容器递归深度是 n那这部分空间就是 O(n)。我记得有人面试时分析“二叉树的递归遍历”说空间复杂度 O(1)因为没开数组——这就是把调用栈给忘了属于典型的翻车现场。同时要分清两种口径。一种是“辅助空间复杂度”指除了存放输入数据本身之外额外申请的内存另一种是“总空间复杂度”把输入数组本身也算进去。很多教材和面试题默认讨论的是辅助空间但你回答时最好主动说明口径避免鸡同鸭讲。比如原地排序辅助空间 O(1)但你要是算上数组本身那至少 O(n)。两种说法都没错关键是把“算的是什么”交代清楚。1.3 为什么大家都爱用大O你可能会问既然有最好情况、最坏情况、平均情况为什么日常交流里大家都只说大 O因为大 O 代表的是“最坏上界”它给了一个安全承诺无论输入怎么刁钻运行成本不会突破这个级别。设计系统时你宁愿高估一点也不敢低估否则线上数据一涨服务就崩了。而且大 O 忽略了常数和低阶项这让不同算法之间的比较变得非常干净。O(n) 就是 O(n)不管它是 2n 还是 100n在 n 足够大的时候它都比 O(n²) 优秀。当然大 O 也有缺点它太粗糙n 很小的时候一个 O(n²) 但常数极小的算法可能比 O(n log n) 但常数巨大的算法更快。复杂度分析给的是方向不是绝对的时间预测。2. 手把手做时间复杂度分析2.1 四条基本规则先把架子搭好做时间复杂度分析之前先立几条规定相当于打地基。第一顺序执行的代码块复杂度相加最后取最高阶。比如先做一个 O(n) 的循环再做另一个 O(n) 的循环总共是 O(n) O(n) O(2n)忽略系数后还是 O(n)。但如果第一个循环 O(n)第二个循环 O(n²)那整体就是 O(n²)。第二嵌套循环的复杂度相乘。外层跑 n 次内层每次跑 n 次基本操作次数就是 n × n n²。这个大家应该熟但真正写代码时内外层变量经常不是完全独立的需要小心。第三分支语句取最坏情况。if 和 else 两条路复杂度不一样分析时默认走更贵的那条路。这和大 O 的定义一致我们关注的是上界。第四去掉常数系数和低阶项。O(2^n n²) 在 n 足够大时n² 根本不值一提直接写 O(2^n)。不要写 O(2n)、O(3n²)直接写 O(n)、O(n²)。2.2 常见代码结构复杂度速查表很多代码模式看一眼就能判断级别我把高频的整理成一张表代码结构典型复杂度说明单个赋值、四则运算、数组按下标取值O(1)与 n 无关for i in range(n) 里的 O(1) 操作O(n)线性扫描每次把规模除以 2 的循环O(log n)二分查找、不断二分外层 n 次、内层 n 次的嵌套循环O(n²)冒泡排序、暴力两数之和归并排序式的分治O(n log n)每一层遍历 n层数 log n子集枚举、组合爆炸O(2^n)每个元素选或不选全排列枚举O(n!)每个位置逐层选择这张表不是让你背的是让你做复杂度分析时有个直觉。拿到一个算法先看它属于哪种结构再用规则推导。2.3 真实推导从一段代码算到 O(n log n)我拿几段伪代码实际推一遍你感受一下套路。先看最简单的def sum_list(arr): total 0 for x in arr: total x return total这个循环执行 n 次每次只有加法所以 O(n)。无论 total 里累加多少它只是一个变量空间上额外占用 O(1)。再看一个容易算错的双层循环for i in range(n): for j in range(i, n): print(i, j)内层次数从 n、n-1、n-2 一直递减到 1总数是 n (n-1) ... 1 n(n1)/2。别被“差一点就不满 n²”骗了n(n1)/2 的最高阶是 n²所以时间复杂度还是 O(n²)。这类“三角循环”在算法题里出现频率很高很多人以为它只有 O(n log n)其实它是 O(n²)。再看二分法lo, hi 0, len(nums) - 1 while lo hi: mid (lo hi) // 2 if nums[mid] target: return mid elif nums[mid] target: hi mid - 1 else: lo mid 1每次循环把搜索区间缩小一半执行 m 次后区间长度变成 n / 2ᵐ当 n / 2ᵐ ≤ 1 时循环结束所以 m ≈ log₂ n时间复杂度 O(log n)。归并排序稍微进阶一点。它的递归式是 T(n) 2T(n/2) O(n)意思是把数组分成两半各自排序最后线性合并。递归树的每一层处理总量都是 n树高 log₂ n因此总复杂度 O(n log n)。2.4 递归别慌递归树和主定理帮你兜底递归的复杂度比循环难因为你得看它展开了多少个节点。最经典的例子是朴素斐波那契def fib(n): if n 1: return n return fib(n-1) fib(n-2)它的时间复杂度和空间复杂度经常被弄混。从递归树角度看每个节点分出两个叉树的深度大约 n节点总数是 1 2 4 ... 2^n也就是 O(2^n)。这个算法慢得离谱原因就在于重复计算太多。但它的递归栈深度只有 n因为同一时刻最多同时存在 n 层调用所以空间复杂度是 O(n)不是 O(2^n)。时间看“总节点数”空间看“递归深度”这是两个维度别混在一起。除了画递归树还有一种更机械的套路叫主定理Master Theorem。不需要背全部结论只要记住最常见的形式T(n) aT(n/b) O(n^d)。把 n^d 和 n^(log_b a) 比较哪个大整体就是哪个相等就在外面乘 log n。归并排序里 a2b2d1log₂21两者相等所以结果是 O(n log n)。主定理应付大部分面试和工程里的分治递归足够了。3. 空间复杂度怎么计算3.1 先定一个口径算辅助空间还是总空间我前面提过口径问题这里展开讲。空间复杂度怎么计算第一步不是数变量而是先问自己要算的是“辅助空间”还是“总空间”。辅助空间不考虑输入数据本身的存储。比如你拿到一个长度为 n 的数组在它内部交换元素做反转没有开额外的等长数组那辅助空间是 O(1)。但如果你定义一个新数组把结果复制进去额外空间的长度是 n那辅助空间就是 O(n)。面试时我建议你把话说完整“这个算法辅助空间复杂度是 O(1)”。这样面试官就知道你清楚输入存储不算额外开销。同时也要意识到很多语言里函数参数传的是引用不复制数组但如果你在函数内部写出了new_arr arr[:]这类复制操作那它就是在申请额外空间藏不住的。3.2 空间复杂度怎么计算的三个抓手变量、容器、递归栈实际计算时只需要盯住三样东西。第一基础类型变量和指针。固定数量的整数、布尔值、引用变量不管 n 多大它们占用的空间都不变每个贡献 O(1)。这里有个细节循环里的临时变量比如 for 循环里存中间结果的变量每次迭代都在复用不是每次迭代都新建一份所以只算 O(1)。第二显式分配的容器。一个长度为 n 的数组是 O(n)一个存了 n 个键值对的哈希表是 O(n)一个 n×m 的二维数组是 O(n·m)。这里要注意很多算法看起来“只用了一个哈希表”但实际上哈希表里存满了数据那它就是 O(n)。第三递归调用栈。每次递归调用都会在系统栈上压入一帧包含参数、局部变量、返回地址。空间复杂度等于“最大递归深度 × 每帧空间”。比如递归深度 n每帧只有 O(1) 变量总空间就是 O(n)如果每帧还持有一个 O(n) 的拷贝数组那就是 O(n²)。3.3 几个高频场景原地、哈希、递归、二维数组我写几个典型例子把上述三样东西串起来。场景一判断数组里有没有重复元素用哈希表def has_dup(arr): seen set() for x in arr: if x in seen: return True seen.add(x) return False时间上是 O(n)因为每个元素进出哈希表平均 O(1)。空间上seen最坏情况下存了 n 个元素所以辅助空间 O(n)。如果你先排序再遍历找相邻重复项排序可能 O(1) 辅助空间总空间要看排序算法时间会变成 O(n log n)。这就是典型的用时间换空间。场景二原地反转数组def reverse_arr(arr): left, right 0, len(arr) - 1 while left right: arr[left], arr[right] arr[right], arr[left] left 1 right - 1每轮只用了两个指针和一次交换没有额外容器辅助空间 O(1)。如果改成arr arr[::-1]那 Python 会新建一个完整列表辅助空间变成 O(n)。场景三递归二分查找。每一层只压一个栈帧深度 log₂ n辅助空间 O(log n)。这个结论很多人想不到因为循环版二分查找的空间明明是 O(1)而递归版多了调用栈开销。场景四二维动态规划。比如求 m×n 网格路径数你开一个同样大小的 dp 数组空间 O(m·n)。但如果状态转移只依赖上一行完全可以只保留两行空间降到 O(n)。这类压缩在动态规划里非常常见本质就是牺牲一部分可读性换空间。4. 实操过程一个真实题目的复杂度分析4.1 题目背景为什么拿“两数之和”当例子题目本身很简单给定一个整数数组nums和一个目标值target找出和为 target 的两个数的下标。之所以选它是因为它能非常清晰地把“暴力循环、哈希优化、排序双指针”三种方案串在一起每个方案的复杂度和决策过程都值得拆解。先约定一下数组长度 n。接下来分别分析暴力版本、哈希版本、排序版本的时间和空间。你会发现同一个问题因为设计取舍不同复杂度差异非常大。4.2 暴力做法O(n²) 时间 O(1) 空间最直接的想法是双重循环枚举所有下标对def two_sum_brutal(nums, target): n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j]内层循环次数从 n-1、n-2 一直递减到 1总数是 (n-1)n/2 ≈ n²/2。忽略常数系数时间复杂度 O(n²)。这也是上一章“三角循环”的实际应用。空间上除了两个下标变量i、j和返回值组成的列表没有额外的容器所以辅助空间 O(1)。如果你在 LeetCode 上提交这个版本小 n 的时候也跑得过去但 n 到几万以后耗时会肉眼可见地暴涨。这就是 O(n²) 的威力输入规模翻倍耗时大约变成原来的四倍。更麻烦的是这个解法在“最坏情况”下几乎要把所有组合都看一遍比如目标值根本不存在时。所以它虽然简单但不是工程上推荐的选择。4.3 哈希优化用空间换时间常见优化是边遍历边查哈希表def two_sum_hash(nums, target): seen {} for i, x in enumerate(nums): need target - x if need in seen: return [seen[need], i] seen[x] i每一次循环只做一次哈希查找和一次插入平均 O(1)所以整体时间复杂度 O(n)。空间上seen最坏存了 n-1 个元素辅助空间 O(n)。这种“空间换时间”的思路在算法题里到处都是本质是用额外存储记住已经见过的信息避免反复扫描。这里的need in seen到底是不是 O(1)取决于底层哈希表是否发生大量冲突。平均情况是 O(1)最坏情况可能退化成 O(n)所以严谨的说法是“平均时间复杂度 O(n)”。但工程上默认哈希表表现良好除非被恶意构造数据攻击。回到决策场景如果内存充足哈希版本几乎一定比暴力快而且代码也不复杂。但如果你面对的是内存极其受限的嵌入式环境O(n) 的辅助空间可能是硬伤。4.4 排序双指针中间路的权衡还有一条路先排序再用双指针从两端向中间逼近。def two_sum_two_pointer(nums, target): sorted_nums sorted(nums) left, right 0, len(sorted_nums) - 1 while left right: total sorted_nums[left] sorted_nums[right] if total target: return [sorted_nums[left], sorted_nums[right]] elif total target: left 1 else: right - 1排序阶段 O(n log n)双指针阶段 O(n)整体时间 O(n log n)。空间取决于排序实现如果原数组不允许被我打乱就要复制一个新数组辅助空间 O(n)如果允许原地排序且语言排序是原地的辅助空间可以压到 O(1)。这个版本的返回值是元素本身而不是原下标要注意题目要求。这个例子很好地说明了一件事复杂度分析不是“算完就完”分析完还要结合场景做决策。n 小的时候暴力可能最快因为常数小n 中等且内存充足哈希最优n 非常大但内存紧张排序双指针可能更稳。5. 常见问题和排查技巧实录5.1 最坏、平均、最好到底哪个才是答案很多人问我复杂度分析到底分析最好情况、平均情况还是最坏情况答案是绝大多数场景默认最坏情况。为什么因为最坏情况给的是“下限保障”你不知道线上用户会传什么数据。比如快速排序平均 O(n log n)但如果每次分区都选到极端 pivot最坏会退化到 O(n²)。你说它是 O(n log n) 还是 O(n²)严谨的说法是平均 O(n log n)最坏 O(n²)。回答面试题时把两种情况都讲清楚比单纯背一个复杂度高级得多。有些算法的平均情况很难严格计算比如各种哈希表操作、红黑树旋转工程上通常直接说期望 O(1) 或 O(log n)心里再留一个“最坏可能退化”的弦。真正要小心的是那些带随机化或提前退出的算法最好和最坏差异巨大。5.2 循环嵌套不等于 O(n²)因为“外层 n 次内层 n 次”所以 O(n²)这只在内层每次都跑满 n 次时成立。实际代码里经常有break、continue、范围缩减、提前返回分析时要看真正的执行次数。举一个常见例子for i in range(n): for j in range(n): if nums[j] target: break如果 target 只在极少数位置命中最坏情况下内外层还是跑满时间复杂度仍然是 O(n²)。但如果你能证明每次内层最多只跑固定次数就退出那整体就是 O(n)。关键不是“有没有 break”而是“最坏条件下 break 是否还成立”。这是很多人分析时最容易犯的错拿平均情况代替最坏情况然后得出过于乐观的结论。还有一种情况外层循环变量不是每次 1而是不断翻倍i 1 while i n: for j in range(n): pass i * 2外层执行 log n 次内层每次执行 n 次整体是 O(n log n)不是 O(n²)。这类“外层对数、内层线性”的模式在算法题里非常常见。5.3 递归栈空间计算尾递归与语言陷阱递归的空间复杂度是新手最摸不着头脑的地方。核心记住一句话空间看深度不看总调用次数。二叉树的前序遍历总节点数是 n但递归栈最深只到树高 h空间是 O(h)。二叉树退化成链表时 hn所以空间 O(n)平衡二叉树 hlog n空间 O(log n)。尾递归值得单独说。如果函数最后一步是递归调用自身且没有额外操作理论上可以优化掉当前栈帧让递归退化成循环空间变成 O(1)。比如阶乘写成return n * fact(n-1)因为有乘法不是尾递归栈深还是 n。写成下面这种传累积参数的形式才是尾递归def fact_tail(n, acc1): if n 1: return acc return fact_tail(n - 1, acc * n)但这里有一个大坑很多语言和解释器并不真正做尾递归优化尤其是 Python。你写一百层递归可能没事写一万层直接RecursionError。所以分析空间时你按尾递归理想情况说是 O(1)实际运行却可能直接爆栈。正确做法是先问清楚目标环境是否支持优化再决定依赖递归还是改写成迭代。5.4 五个容易翻车的复杂度判断习惯我总结了五个我见过无数人踩过的坑自己也踩过几个第一只看循环层数不看循环体内是否调用了复杂函数。很多语言里字符串拼接看起来是 O(1) 的实际每轮可能要复制整个字符串导致整体从 O(n) 变成 O(n²)。同理循环里调in array这种线性查找会让复杂度多乘一个 n。第二把常数优化当成降阶。比如某个循环只要跑 n/2 次你写成 O(n)没问题但你不能说“我优化成了 O(n/2)”复杂度里没有 O(n/2) 这种说法。真正的降阶是把 O(n²) 变成 O(n log n)把 O(n) 变成 O(log n)。第三忽略最坏输入的构造。有的算法平时很快一旦碰上特殊输入就打回原形。比如快速排序遇到逆序数组、哈希表遇到大量同哈希数据、动态规划题目里没注意状态范围。分析时必须明确“最坏输入能不能构造出来”。第四把输入规模定义搞错。复杂度里的 n 不是“有几行代码”而是输入规模。两个数组 m 和 n分析要写 O(mn) 或 O(m×n)不能想当然都叫 n。字符串算法里 n 指长度大整数运算里 n 往往指位数位数增加一位开销可能变化非常大。第五空间只算显式容器漏算递归栈和函数调用参数。前面递归的例子已经说得很清楚了这里再强调一遍深入分析之前先确认算法有没有隐藏的调用栈开销。5.5 用实测验证复杂度倍增法观察变化趋势复杂度分析是理论实际运行是实践。如果我能跑测试我会用“倍增输入规模”的方式验证自己判断得对不对。原理很简单把输入规模从 n 扩大到 2n看耗时变化。如果耗时大致变成原来的 2 倍大概率是 O(n)变成 4 倍大概率是 O(n²)变成 1.1 倍到 1.2 倍之间大概是 O(log n) 或者增长很慢的级别变成 2 倍多一点可能是 O(n log n)。因为 n log n 当 n 翻倍时约等于原来的 2×(log(2n)/log n) 倍这个倍数会缓慢向 2 靠拢。Python 里可以用timeit做粗测也可以用tracemalloc看内存增长。但实测结果只能当参考因为机器负载、CPU 缓存、垃圾回收都会干扰。有一次我在本地测一个 O(n log n) 的排序n 翻倍后耗时居然只长了 1.3 倍我还以为判断错了后来才发现是缓存命中带来的假象。所以正确姿势是先做理论分析再用实测验证两者不一致时优先回头审视理论哪一步出了问题。6. 我自己的一些做法分享一个我后来养成的小习惯写任何算法之前先在最上面用注释写清楚预期复杂度再动手。别小看这个动作它逼着你在开始写代码前就想清楚循环层数、递归深度、额外容器而不是写完再回头分析。我发现很多“想当然”的解释在注释的一瞬间就暴露了。另外做完复杂度分析后我习惯顺手问自己一个问题这个复杂度是“最好的”吗还有没有更优解如果我能证明当前已经是最优比如必须看一遍全部数据所以至少 O(n)那心里就踏实了。如果证明不了说明可能还有更聪明的方案。数据结构与算法学到后面拼的就是这口气不是背答案而是对时间和空间的变化保持敏感。希望这些经验能帮你少走一些我当年走过的弯路。