先把结论放在这里算法复杂度不是背出来的是算出来的。我见过太多准备考研复试或者秋招面试的同学能把快排O(n log n)、堆排O(n log n)、冒泡排序O(n²)背得滚瓜烂熟但一问“为什么快排最坏情况是O(n²)”或者“折半查找为什么是O(log n)”立刻就卡壳。这种状态应付背诵题勉强够用但408统考、名校复试、大厂笔试里那些变着花样的复杂度题基本就是送分题变送命题。这篇文章就把数据结构与算法里最基础也最重要的算法复杂度拆开讲一遍覆盖期末复习、考研、面试准备和自学入门四个场景带着你从“背结论”升级到“会推导”。不管你看的是《大话数据结构》《数据结构与算法分析Java语言描述》还是北大那套Python数据结构与算法视频课复杂度都是第一道门槛。这道门槛迈不过去后面排序、查找、图、动态规划学得越深越痛苦因为每个高级算法都在用复杂度语言说话。反过来把复杂度这套思路吃透你会发现很多算法之间的优劣关系一眼就能看穿学习效率完全是两个量级。1. 复杂度到底在衡量什么三个被忽视的前提1.1 它衡量的是增长趋势不是运行秒数很多人一开始会把时间复杂度和“程序跑了多少秒”划等号这是最常见的误解。时间复杂度描述的不是具体的运行时间而是操作次数随输入规模增长的变化趋势。举个例子就清楚了。假设程序A处理100条数据需要0.01秒处理1000条需要0.1秒处理10000条需要1秒。数据量翻10倍时间也翻10倍这是线性增长。程序B处理100条0.01秒处理1000条0.2秒处理10000条要4秒数据量翻10倍时间翻了20倍、40倍这是平方级增长。复杂度记载的就是“翻倍之后会怎样”这种增长规律而不是哪一次具体跑了多少毫秒。这就解释了为什么复杂度分析里经常要把常数项、低阶项全部扔掉。因为当n足够大的时候决定命运的是增长最快的那个主导项。n²加上一万个常数项在n取到一百万时那点常数早就被淹没了。1.2 输入规模n到底指什么分析复杂度之前先要搞清楚n是什么。对数组操作n通常是元素个数对字符串匹配n是字符串长度对图算法n就变成了顶点数V和边数E这就是为什么图相关的复杂度经常写成O(VE)或者O(V log V E)。这里要特别提醒考研和面试的同学图算法里只说“O(n²)”或者“O(n)”是不严谨的必须说清楚n是顶点数还是边数。408统考里图那一章经常在这里挖坑邻接矩阵存图遍历所有边就是O(V²)邻接表存图遍历所有顶点和边就是O(VE)。同样一道题存储结构不同复杂度表达方式完全不同这就是为什么复习时不能只背公式要能把“n代表什么”一起说清楚。1.3 最好、最坏、平均三个口径要分清同一个算法在不同输入下的表现可能天差地别。最典型的就是顺序查找目标元素在数组第一位一次比较就找到最好情况O(1)目标在最后一位或者压根不存在要比较完整个数组最坏情况O(n)每个位置等概率出现平均要比较(n1)/2次平均情况O(n)。三种口径里考试和面试默认说的“时间复杂度”通常指最坏情况因为最坏情况给出了算法的性能上限是承诺、是底线。但有些算法必须在三个口径之间切换着看。比如快速排序平均情况O(n log n)最坏情况却会退化到O(n²)插入排序最坏O(n²)但最好情况只有O(n)。搞清楚题目问的是哪个口径比会算本身更重要我见过太多人不是不会算是压根没看题问的是什么。提示期末和考研复习时凡是牵涉到排序、查找的复杂度结论先问自己三件事——n指什么、说的是最好还是最坏还是平均、为什么是这个量级。三件事都能答出来这个知识点才算真正是你的。2. 大O表示法的直觉与边界别被数学定义吓住2.1 大O说的是“不会超过某个增长速度”大O的数学定义是存在正常数c和n₀使得当n ≥ n₀时f(n) ≤ c·g(n)就记作f(n) O(g(n))。翻译成人话就是当输入规模足够大之后你的算法操作次数最多也就是某个常数倍的g(n)那么多。这里的关键动作是“丢掉常数因子丢掉低阶项”。为什么可以丢因为大O关心的是n趋近无穷时的渐进行为。比如f(n) 3n² 100n 10000当n 1万时3n²是3亿100n是100万10000是1万低阶项只有主导项的0.3%。当n更大时这个比例进一步缩小所以f(n) O(n²)。这个“足够大”的分界点在数学上就是n₀在实际工程里可能就是几千、几万、几百万取决于你的数据规模。2.2 理论O(n²)的算法在小数据上可能秒杀O(n log n)的算法大O掩盖了常数因子这在理论分析里是优点在实际工程里却会造成一个反直觉的现象复杂度差一个量级的算法在小规模数据上不一定更慢。插入排序是O(n²)归并排序是O(n log n)听起来归并全面碾压。但如果n只有50插入排序那点常数开销极其小而归并排序要分配辅助数组、要递归、要做合并操作常数因子大得多实际跑起来插入排序反而更快。这也是为什么很多标准库的快排实现里有一个优化当子数组长度小于某个阈值比如16、32时不再递归快排而是直接切换到插入排序。复杂度分析管的是大局工程落地还得看常数。2.3 常见复杂度量级的感性认识光看符号很难建立直觉我给一张表假设每一步操作耗时1纳秒看看n取不同值时各量级大概要算多少次复杂度n10n100n1000O(1)1步1步1步O(log n)约3步约7步约10步O(n)10步100步1000步O(n log n)约33步约664步约9966步O(n²)100步1万步100万步O(2ⁿ)1024步无法完成无法完成这组数字值得多看几遍。O(n²)从10到100操作次数从100涨到1万还扛得住O(2ⁿ)从10涨到20操作次数从1024涨到上百万涨到30就直接过十亿。这就是为什么说指数级的算法只存在于理论中n稍微大一点什么机器都救不回来。排序算法的复杂度结论是期末和面试的高频考点我把最常见的几个整理成一张表标注了最好、平均、最坏、辅助空间和稳定性复习的时候照着这张表自查排序算法最好平均最坏辅助空间稳定性冒泡排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n)O(n²)O(n²)O(1)稳定希尔排序O(n log n)视间隔序列而定O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n) ~ O(n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定这张表是结论但光背结论不够。希尔排序的最坏复杂度为什么是O(n²)快排最坏为什么退化归并为什么稳定但空间开销大这些推导在后面几章会一个一个讲到。3. 手把手推导从循环、嵌套到二分查找的完整过程3.1 单层循环复杂度统计的基本口径先看最简单的场景一段单层循环for i in range(n): print(i)循环体print(i)执行n次每次是一个常数时间操作。总操作次数是n的常数倍所以时间复杂度O(n)。这里需要建立一个统计口径所谓“操作次数”统计的是基本操作。基本操作包括算术运算、比较、赋值、访问数组元素这类可以在常数时间内完成的操作。严格说大整数运算、大数比较的成本跟数字位数有关但在数据结构与算法分析的标准模型里我们统一按常数时间处理。这个抽象模型是复杂度分析的前提考研和面试默认如此不用纠结。再看一个稍微变形的例子count 0 for i in range(n): count i print(count)循环体里有加法和赋值还有一个print一共做了3个常数操作。总操作次数约等于3n写成大O还是O(n)。这就是为什么我说复杂度不是背出来的——你可以精确数出3n、5n还是100n但大O统一收敛到O(n)常数因子被吃掉。3.2 嵌套循环加法原理与乘法原理嵌套循环是O(n²)的主要来源但很多人不知道“为什么是n²”只会背结论。来看这个经典写法for i in range(n): for j in range(n): print(i, j)外层循环n次每次外层迭代内层循环完整跑n次总操作次数n × n n²。乘法原理嵌套循环的复杂度是各层循环次数的乘积。变种1内层从i开始for i in range(n): for j in range(i, n): print(i, j)外层第i次迭代时内层循环n - i次。总次数是n (n-1) (n-2) ... 1 n(n1)/2展开是(1/2)n² (1/2)n。大O取主导项还是O(n²)但常数因子比“n层套n层”的写法小了一半。实际运行它大约快一倍复杂度量级却没变。变种2外层平方循环套内层线性循环for i in range(n * n): for j in range(n): print(i, j)外层n²次内层n次总操作次数n³O(n³)。这种题目在期末卷子里出现频率很高关键就是看清每层循环的边界是n、n/2、n²还是log n。3.3 折半查找O(log n)的完整推导过程折半查找二分查找是考研数据结构里出镜率极高的例题也是把“对数复杂度”讲得最透彻的例子。前提是有序数组每次取中间元素比较目标小则去左半目标大则去右半。def binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1推导过程是这样的初始区间长度n第一次比较后区间变成n/2第二次变成n/4第k次变成n/(2ᵏ)。最坏情况下区间长度收缩到1时还要再做最后一次比较才能确定结果。所以需要满足n/(2ᵏ) ≤ 1解得k ≥ log₂n。加上最后一次比较总次数是⌊log₂n⌋ 1取大O就是O(log n)。这里多说一句为什么代码里mid (left right) // 2而不写成(left right) // 2之外的某种形式因为当数组很大时left right可能溢出整数范围严谨的写法是left (right - left) // 2。这不是复杂度问题是工程健壮性问题面试里主动提出来能加印象分。折半查找的威力在于数据规模越大优势越明显。n 100万时顺序查找平均要比较50万次折半查找最多只需要20次左右。这个差距是数量级的不是快几倍的问题。注意复杂度推导里log的底数到底是2、10还是e在大O表示法里没有任何区别。因为log₂n和log₁₀n之间只差一个常数倍log₂10而常数因子会被大O吃掉。这就是为什么统一写成O(log n)就够了。3.4 三个复杂度结论的对比从循环推导中看到的规律对比前面这几个推导能总结出一个规律单层循环是O(n)嵌套循环是O(n²)区间不断减半的循环是O(log n)。这个规律可以推广到绝大多数基础算法。后面学归并排序时看到O(n log n)其实就是“外层区间减半log n层 内层线性合并每层n”的组合。把这个骨架记在心里比死记任何复杂度的数值都有用。再给一个常考的小陷阱循环变量每次乘以2而不是加1。i 1 while i n: i i * 2循环次数是1, 2, 4, 8, ..., 2ᵏ当2ᵏ ≥ n时停止所以k log₂n复杂度O(log n)。如果把i i * 2改成i i * 3那就是log₃n仍然是大O意义上的O(log n)。这种题在408和期末复习里反复出现考点就是“乘法增长对应对数复杂度”。4. 递归复杂度与主定理两类必考场景的拆解4.1 递归树归并排序的O(n log n)是怎么长出来的递归算法的复杂度不能像循环那样直接数循环次数需要用递归树或者递推式。最经典的例子是归并排序递推式写出来是T(n) 2T(n/2) O(n)意思是规模n的问题拆成两个规模n/2的子问题每层合并的成本是O(n)。画出递归树第一层1个节点规模n合并成本O(n)第二层2个节点规模n/2合并成本2 × O(n/2) O(n)第三层4个节点规模n/4合并成本4 × O(n/4) O(n)第k层2ᵏ个节点规模n/(2ᵏ)每层总成本仍然是O(n)这里的关键是无论在哪一层所有节点合并工作量的总和都是O(n)。这就像一个公司的管理层总裁管两个人两个人各管两个人层级越往下人越多但每个人管的范围越小每层“总的协调成本”反而差不多。层数是多少从n一路除以2到1一共log₂n层。每层O(n)总共log₂n层所以归并排序的时间复杂度是O(n log n)。4.2 主定理考研复试都爱考的三句话递归式求复杂度除了画递归树还有一条更机械化的路主定理。它适用于形如T(n) aT(n/b) f(n)的递推式意思是一个规模n的问题被拆成a个规模n/b的子问题拆分的额外成本是f(n)。主定理把f(n)和n^(log_b a)比较三种情况情况条件结论情况1f(n) O(n^(log_b a - ε))T(n) Θ(n^(log_b a))情况2f(n) Θ(n^(log_b a))T(n) Θ(n^(log_b a) log n)情况3f(n) Ω(n^(log_b a ε)) 且满足正则条件T(n) Θ(f(n))这个表格刚看会很抽象我配三个具体例子就通了归并排序T(n) 2T(n/2) O(n)这里a2, b2, log_b a 1。f(n) n正好等于n¹命中情况2所以T(n) Θ(n log n)。和递归树推出来的一致。二叉树遍历T(n) 2T(n/2) O(1)log_b a 1f(n) O(1) O(n^(1-ε))命中情况1T(n) Θ(n)。意思就是每个节点访问一次线性时间符合直觉。折半查找的递归写法T(n) T(n/2) O(1)a1, b2, log_b a 0f(n) O(1)正好等于n⁰命中情况2T(n) Θ(log n)。这也和前面迭代版推导一致。主定理有一个重要边界f(n)和n^(log_b a)必须在“多项式意义”上可比。也就是说差距必须是n的某个正数次幂不能只是log n这种缓慢的差距。比如T(n) 2T(n/2) n log nf(n) n log n 和 n^(log_b a) n之间差了一个log n因子不满足主定理三种情况的任何一个实际答案是Θ(n log²n)但主定理推不出来。这种题目在期末试卷里属于拔高题会做是加分项不会也正常但至少你要知道“主定理不是万能的”。4.3 斐波那契数列同一个问题两个复杂度量级递归和迭代的复杂度对比斐波那契数列是最经典的例子没有之一。朴素递归写法def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)递推式T(n) T(n-1) T(n-2) O(1)。画递归树可以看到每次调用分裂成两个子调用递归树近似一棵满二叉树节点数是指数级别的所以时间复杂度O(2ⁿ)。n 40的时候大约要做十亿次级别的调用肉眼可见的卡顿。改成循环def fib(n): a, b 0, 1 for _ in range(n): a, b b, a b return a单层循环O(n)。从O(2ⁿ)降到O(n)这个优化幅度是最极端的那种指数级变线性级。面试官问“你做过什么算法优化”拿这个例子讲比背一堆八股文有说服力得多。提示斐波那契递归版的时间复杂度准确说是O(斐波那契数增长速率)即O(φⁿ)φ约等于1.618。写O(2ⁿ)是保守上界写Θ(φⁿ)更精确考试写O(2ⁿ)完全没问题因为2ⁿ比φⁿ增长更快大O允许给宽松上界。5. 空间复杂度面试和考试里最容易被低估的考点5.1 空间复杂度的统计口径到底算不算输入本身时间复杂度和空间复杂度是一对孪生概念但很多教材对空间复杂度着墨甚少导致它成了考试和面试里最容易翻车的点。空间复杂度衡量的是算法运行过程中额外需要的内存大小随n增长的变化趋势。这里有一个必须明确的统计口径输入数据本身占用的空间默认不算进空间复杂度。因为无论什么算法输入都要存在那里这部分不是算法“制造”的成本。空间复杂度说的是辅助空间也就是算法为了完成计算额外开辟的内存。考试题目里如果写“包括输入空间”或者“就地算法”那是特例否则一律默认统计辅助空间。比如三个最简单的O(n²)排序——冒泡、选择、插入辅助空间都是O(1)因为它们交换元素时只需要一个临时变量。这里容易出判断题把选择排序说成“需要O(n)辅助空间”就错了因为选择排序是在原数组上操作所谓“选择”只是记录最小值下标并没有额外拷贝整个数组。5.2 递归的空间成本栈帧怎么数递归算法的空间复杂度计算和迭代完全不同。每调用一次递归函数系统就在调用栈上压入一个栈帧栈帧里保存局部变量、参数和返回地址。递归深度是多少栈里就同时存在多少层栈帧。回到斐波那契的例子。递归版虽然时间复杂度O(2ⁿ)但空间复杂度并不是O(2ⁿ)。你画递归树时看到指数级节点但这些节点不是同时存在的——函数执行完一条分支后栈帧就弹出释放了。整个过程里调用栈最深只到n层左右沿一条链从fib(n)一路调到fib(1)所以空间复杂度是O(n)。这个问题我在集体辅导时几乎每次都有人踩记住了空间复杂度看的是“同时存在”的栈帧数量不是历史上调用过的总次数。归并排序也是同样的道理。它需要O(n)的辅助数组做合并这部分空间扫一眼代码就能数出来递归深度最坏log₂n层空间是O(log n)。加在一起通常记作O(n)因为辅助数组的O(n)是主导项。快速排序就不一样了它不需要辅助数组但递归带来的栈空间最好情况和平均情况是O(log n)最坏情况会退化到O(n)每次划分极端不平衡递归深度变成n。这就是为什么排序复杂度表里快排的空间那栏写着O(log n)到O(n)。5.3 空间换时间工程里每天都在做的交易空间复杂度的意义不只是考试要算更重要的是它在工程里直接对应成本。哈希表是空间换时间最典型的产品额外开O(n)的桶数组换来平均O(1)的查找、插入、删除。对比链表链表在内存利用上很“抠”插入删除O(1)但查找要O(n)。如果你要频繁查找哈希表那点空间开销绝对是划算买卖。我自己做数据处理时有个习惯凡是代码里出现“先排序再查找”或“双重循环查找”的地方先停下来算一笔复杂度账。n到一万级别O(n²)还能硬扛n到百万级别双重循环基本跑不动这时候要么换哈希表、要么排序后二分查找空间多花一点时间省下来一个数量级。这种取舍思想也是面试官在系统设计题里真正想考察的东西能不能在时间和空间之间找到平衡点而不是只会背“哈希表O(1)查找”这个结论。6. 工程视角的复杂度应用均摊分析、对数底数与常见误区6.1 均摊分析动态数组扩容为什么还算O(1)有一种复杂度问题很反直觉动态数组的append操作。Java的ArrayList、C的vector、Python的list底层都是动态数组容量不够时申请一块更大的内存把所有元素拷贝过去。单看某一次触发扩容的append代价是O(n)——要把已有n个元素全部拷到新数组。可如果按“最坏情况O(n)”来评价动态数组的append那工程里就不会有人用了。这里要用均摊分析。假设容量满时翻倍从容量1开始扩容发生在1、2、4、8、16...等时刻每次扩容的拷贝成本分别是1、2、4、8、16...执行n次append总拷贝成本是124...约等于2n。n次操作总成本约3nn次赋值加2n次拷贝平均到每次操作上均摊复杂度O(1)。均摊分析的思维方式是“把贵操作的账平摊到所有便宜操作上”。它和大O的“最坏情况”不同更适合评价一个结构在持续使用中的综合表现。面试里问“动态数组push_back为什么均摊O(1)”很多人答不上来其实就这么一句话扩容次数是log n级别的总拷贝成本被n次操作摊薄了。6.2 三个常见的复杂度误区误区一以为O(log n)的底数很重要。我在前文已经提过大O吃掉常数因子log₂n和log₁₀n只差常数倍所以底数无所谓。但很多教材推导归并排序时写log₂n有人就记住了“归并的复杂度是log以2为底”换一道题出现ln就慌了。大可不必统一O(log n)就行。误区二以为O(1)就是快。O(1)只表示“不随n增长”不代表常数本身小。哈希表的O(1)查找要先计算哈希值、处理冲突常数因子可能比顺序查找的一次比较大得多。n很小时哈希表未必比线性扫描快。这就是为什么很多标准库对小型容器直接用线性搜索而不是上哈希。误区三以为复杂度低的算法在任何数据规模下都更快。前文说过归并排序O(n log n)在小数据上跑不过O(n²)的插入排序因为递归、建栈、合并这些操作带来了巨大的常数开销。工程实现里混合排序策略就是基于这个原理——大数据分治小数据插入。评估一个算法好不好复杂度是核心指标但不是唯一指标。6.3 期末、考研408、面试三种场景下复杂度怎么学期末复习的场景重点在“算”。把单层循环、嵌套循环、折半查找、递归树、主定理三种情况都亲手推一遍再把排序算法的复杂度表从头推导刷新一次基本就能覆盖90%的题型。数据结构实验报告里老师要求写的“算法分析”部分也就是把时间复杂度和空间复杂度算清楚步骤一般是确定基本操作、列出循环或递归结构、求和或列递归式、写复杂度结论。按这个模板来实验报告这部分拿满分不难。考研408的场景重点在“全”。408喜欢跨章节考复杂度比如图算法里“用邻接矩阵实现的Dijkstra复杂度是多少”“用邻接表实现又是什么量级”或者“散列表的查找复杂度在什么条件下是O(1)”。这些题目考察的不只是复杂度公式而是数据结构和复杂度之间的联动关系。复习时建议每学完一种结构都把查询、插入、删除三个操作的复杂度单独写出来和数组、链表、树、图、散列表放在一起对比。面试的场景重点在“讲”。面试官抛出复杂度问题时不要只扔一个O(n log n)的结论而是用一句话解释来龙去脉先说从递推式T(n) 2T(n/2) O(n)出发然后说递归树每层的成本是O(n)、总层数是log n所以得到O(n log n)。这个回答结构能把“背答案”和“懂原理”一眼区分开。到这里你会发现算法复杂度本质上是一种“用数学语言描述资源消耗增长规律”的思维方式。它贯穿数据结构学习的每一个章节也是连接理论和工程实践最直接的一座桥。以我个人的经验把复杂度真正学通的人学后面的排序、查找、动态规划、图算法都会有一种“原来如此”的顺畅感。建议你从今天开始每学一个新算法先别看书上的复杂度结论自己拿循环结构或者递归树推一遍推完再对着标准答案核对。坚持一两个月你会发现那些曾经需要死记硬背的复杂度表格现在已经牢牢长在你脑子里了。