学数据结构的时候我见过太多这样的同学链表反转能默写二叉树遍历代码滚瓜烂熟但一被问到你这个算法时间复杂度是多少就当场愣住支支吾吾说应该是O(n)吧。问为什么答感觉是O(n)。再看空间复杂度更是稀里糊涂经常把递归的空间算成变量就那几个所以O(1)。说实话这个状态在考研408、期末考和面试里都非常吃亏。复杂度分析不是靠感觉也不是靠背结论它本质上是在做一件很朴素的事数基本操作被执行的次数再把这个次数和问题规模n的关系翻译成大O记号。这篇就用数据结构里最常见的几类代码当例子从单层循环讲到递归、再讲到二叉树和排序把算法时间复杂度和空间复杂度的推算过程完整过一遍。适合正在复习期末、准备考研408或者刷题时老是被问复杂度却答不上来的同学。我尽量把每一步推导都写出来看完你再去面对那些手推复杂度的题心里会踏实很多。1. 先想明白复杂度分析到底在数什么1.1 问题规模 n 定错了后面全白算拿到一段代码第一件事不是看循环而是问自己这个算法的输入规模变量是什么对数组操作规模通常就是数组长度n对矩阵操作规模可能是矩阵阶数n也可能是一个n×n矩阵里的元素总数对字符串操作规模是字符串长度对图结构规模是顶点数V和边数E。这个变量一旦定错后面所有推导都是错的。我之前带过一个学弟他自己写了一个冒泡排序分析复杂度时把规模写成了元素的数值大小得出一个离谱的结论。他忘了冒泡排序处理的是长度为n的数组排序所用的比较、交换次数只和数组长度有关和元素具体是3还是100000完全无关。所以第一课很简单先找出n是什么再开始数次数。1.2 基本操作从执行次数最多的语句下手一段程序里有赋值、加法、比较、循环条件判断、函数调用你不可能把每一句都精确数一遍再相加。实际上复杂度分析关心的是增长趋势所以我们只需要挑出执行次数最多、且随n增长最快的那条或那几条核心语句数它的执行次数就够了。这条语句叫基本操作或者叫关键操作。举个例子int sum 0; for (int i 0; i n; i) { sum a[i]; }这条程序里sum a[i]执行了n次i执行了n次i n执行了n1次sum 0和int i 0各执行1次。精确加起来是3n 3次。但你会发现不管n取多大执行次数占绝对大头、增长最快的就是sum a[i]所在的循环体。所以基本操作就是它执行次数是n时间复杂度为O(n)。可能有人问i n明明也执行了n1次为啥不把它当基本操作因为它和sum a[i]是同一个数量级的都是n次选哪个结果都一样。真正要避免的是把sum 0这种每次只执行一次的语句当基本操作那样你数出来的就是O(1)完全掩盖了循环的主导地位。1.3 大O记号怎么用抓大放小扔掉常数大O记号的定义如果按教科书说是存在正常数c和n0使得当n ≥ n0时T(n) ≤ c·f(n)那么称T(n) O(f(n))。这个定义很多人看了就头大我用大白话解释**当n足够大以后你的算法运行时间可以被另一条简单曲线按住这条曲线就是f(n)。**什么常数系数、低阶项、后面拖油瓶的加数通通不重要因为n大了它们的影响会被放大到忽略不计。比如刚才的3n 3你完全可以找到c 6让3n 3 ≤ 6n对n ≥ 1恒成立所以它是O(n)。再比如n² 5n 10n足够大时5n 10相比n²就是毛毛雨直接丢掉结果是O(n²)。生活里类比一下你从1写到n写得快慢只是斜率不同但无论如何总时间都和n成正比画出来都是一条直线真正让曲线从直线变成抛物线的是嵌套循环或递归这类结构。大O就是看这条曲线最终属于什么形状而不是看它斜率多陡。有了这个基础下面就可以开始拿例子练手了。2. 循环结构从单层循环到 i*i复杂度手推一次就通2.1 单层for循环O(n)与n1陷阱先来一个最简单的int count 0; for (int i 0; i n; i) { count; }基本操作count一共执行n次所以时间复杂度O(n)。这个几乎没人会错。但换个写法很多人就犹豫了for (int i 0; i n; i) { count; }区别只是i n变成了i n基本操作执行n1次。那么时间复杂度是O(n1)吗严格地说精确执行次数是n1但写成大O就是O(n)因为常数1在n面前可以忽略。反过来说如果你是在做精确计数的题目那要注意这个1很多408选择题专门考循环体执行多少次此时i n和i n能差出一次。这里我想多说一句O(n)不意味着循环体一定执行n次而是和n成正比。2n、3n5、n/2这些在大O记号里统统都是O(n)。真正能把时间复杂度从O(n)变成别的量级的靠的是循环层数变多或者循环变量的增长速度发生变化。2.2 双层循环两个版本满循环与三角形循环都是O(n²)吗双层循环是考研和面试的重灾区先看最标准的for (int i 0; i n; i) { for (int j 0; j n; j) { count; } }外层i从0到n-1每来一个i内层j都要从0到n-1跑一遍。所以count执行n × n n²次复杂度O(n²)。再看下面这个稍微隐蔽一点的选择排序的核心结构for (int i 0; i n; i) { for (int j i 1; j n; j) { // 比较或交换操作 count; } }外层i 0时内层执行n-1次i 1时内层执行n-2次……一直到i n-1时内层执行0次。所以总次数是(n-1) (n-2) ... 1 0 n(n-1)/2n(n-1)/2展开是(n² - n)/2按大O记号去掉常数1/2再去掉低阶项n结果就是O(n²)。所以这个三角形双层循环也是O(n²)和满循环在数量级上没有区别。冒泡排序、选择排序、插入排序最外两层都是这个结构所以它们都是O(n²)级别。掌握等差数列求和这个工具很多双层循环的推导都能一次算对。2.3 改变步长的循环O(logn)与O(√n)从哪来不是所有循环都一个点一个点往后挪看这个int k 1; while (k n) { // 做 O(1) 的事 k k * 2; }k的变化是1、2、4、8......每次翻倍。问循环体执行几次假设执行了t次那最后一次循环结束后k约等于2^t它必须满足2^t ≥ n才能跳出循环所以t ≈ log2n。这就是O(logn)的来源。二分查找为什么快因为它每轮把搜索区间砍一半执行的轮数就是log2n而不是n。这里有个小知识**O(logn)到底是以2为底还是以10为底无所谓。**因为log2n和log10n之间只差一个常数倍在大O记号里常数倍被吸收掉了所以直接写O(logn)。还有一类循环条件带乘方也常被忽视for (int i 1; i * i n; i) { count; }很多人一看这不就是个单层for吗直接写O(n)。错了你看条件i*i n说明i最大只能到√n。所以循环体执行次数是√n次复杂度O(√n)。判断一个循环的复杂度千万不要只看它有几层for关键要看循环变量每次怎么变、循环条件受什么约束。这两处才是决定复杂度的真正开关。3. 递归的时间复杂度递归树比公式直观得多3.1 阶乘T(n)T(n-1)O(1)递归的时间复杂度分析很多同学觉得难是因为不知道从哪里下手。我教一个朴素有效的办法把递归调用画成一棵树一个节点代表一次函数调用看这棵树上有多少个节点以及每个节点要做多少O(1)的事。先看最简单的递归求阶乘int fact(int n) { if (n 1) return 1; return n * fact(n - 1); }fact(n)会调用fact(n-1)fact(n-1)会调用fact(n-2)一直到fact(1)为止。这是一条直链节点数就是n。每个节点内部只做一次乘法和一次递归调用也就是O(1)的工作量。所以总时间 节点数 × 每个节点工作量 n × O(1) O(n)。这种一长条的递归本质上就是把循环用函数调用写出来时间复杂度常常和循环版一样。真正让它复杂起来的是一个节点分叉出两个子调用的情况。3.2 斐波那契为什么朴素递归是O(2^n)教科书里的经典反面教材int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }fib(n)一进来就调用fib(n-1)和fib(n-2)。这两个子问题又会各自接着分叉。画一下递归树fib(n-1)下面挂着fib(n-2)和fib(n-3)fib(n-2)下面挂着fib(n-3)和fib(n-4)。树的深度大约到n每一层都会比上一层多出接近一倍的节点整棵树的节点总数就是指数级别的。更严谨的推法是写出递推式T(n) T(n-1) T(n-2) O(1)这个递推式的解是O(2^n)。不信你从 n1 到 n10 去数一下fib被调用了多少次n10时远远超过1000次n20时就超过一万次了。这就是为什么朴素斐波那契在n稍微大一点就跑不动的原因。注意这里有个很常见的误区时间是O(2^n)不代表空间也是O(2^n)。空间复杂度要看某一时刻系统栈最多压了多少层而不是一共创建了多少个栈帧。递归调用是深度优先的fib(n)会先沿着fib(n-1) → fib(n-2) → fib(n-3)一路挖到底这时候栈深度达到n等它一层层返回再处理另一条分支时栈是复用之前释放掉的位置的。所以朴素斐波那契的空间复杂度其实是O(n)不是O(2^n)。这一点我见过太多人写错考研复习时务必留意。3.3 归并排序与快速排序分治的两种复杂度走向分治类算法的高频代表就是归并排序和快速排序。先看归并排序的递归框架void mergeSort(int arr[], int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid 1, r); merge(arr, l, mid, r); // 合并两个有序区间耗时 O(n) }每层递归把长度为n的区间对半分成两个长度为n/2的子区间然后合并时要把两个子区间扫一遍线性时间O(n)。所以递推式是T(n) 2T(n/2) O(n)这个递推式怎么解画递归树第一层是1个规模n的问题合并成本O(n)第二层是2个规模n/2的问题合并成本总共也是O(n)第三层是4个规模n/4的问题合并成本还是O(n)。一直分到规模为1一共有log2n层每层成本都是O(n)。因此总时间 层数 × 每层成本 O(nlogn)。快速排序有点特殊。它的递推式是T(n) T(k) T(n-1-k) O(n)这里k是基准元素最终位置左边的元素个数。理想情况下基准刚好把数组劈成两半k ≈ n/2那和归并排序一样是O(nlogn)。可如果数组本来就有序你每次选的基准又是第一个元素那么左边是0个、右边是n-1个递推式退化成T(n) T(n-1) O(n)这就变成一个节点只带一个孩子的直链时间复杂度变成O(n²)。所以快速排序平均情况O(nlogn)最坏情况O(n²)而且这个最坏情况在工程上真能遇到这也是为什么快排的实现里要加三数取中随机选取基准这些优化。以后面试别人问快速排序复杂度你如果只说O(nlogn)等于只答了一半。4. 空间复杂度最容易丢分的系统栈和额外数组4.1 原地算法反转链表和逆置数组的O(1)空间空间复杂度计算的核心是看除了问题输入本身占用的空间外你额外开了多少辅助空间。辅助空间是常数级别就说空间复杂度O(1)辅助空间大小和n成正比就是O(n)。最典型的O(1)空间例子单链表原地反转struct ListNode* reverse(struct ListNode* head) { struct ListNode *prev NULL, *cur head; while (cur) { struct ListNode *next cur-next; cur-next prev; prev cur; cur next; } return prev; }整个过程只用到了prev、cur、next三个指针无论链表有多长额外空间都是3个指针不变。所以空间复杂度O(1)时间复杂度O(n)。像这种边遍历边改指针、边遍历边交换的做法在刷题术语里叫原地算法。凡是能用原地算法解决的题面试官通常默认你优先考虑它因为它空间效率最高。数组原地逆置也是一样的思路void reverseArray(int a[], int n) { for (int i 0; i n / 2; i) { int temp a[i]; a[i] a[n - 1 - i]; a[n - 1 - i] temp; } }只多了一个临时变量temp空间O(1)。4.2 递归的空间账斐波那契虽然调用次数多空间却是O(n)写递归分析空间复杂度是期末考扣分的重灾区。记住这句话递归的空间复杂度 递归的最大深度 × 每一层递归的辅助空间。为什么是最大深度而不是调用总次数因为递归调用不是同时存在的。函数fact(n)调用fact(n-1)时fact(n)并没有执行完它的栈帧还留在系统栈里等fact(n-1)返回后接着用。所以在某一瞬间系统栈里同时存在的栈帧数等于当前递归路径的深度而不是累计创建过的栈帧总数。拿阶乘递归来说fact(n)要等fact(n-1)返回而fact(n-1)要等fact(n-2)返回... 最深的那一瞬间栈里从fact(n)到fact(1)一共n层每层只存几个局部变量和返回地址O(1)。所以空间复杂度 n × O(1) O(n)。回到斐波那契虽然总共调用了指数级别的次数但它的最大递归深度只有n沿着一条分支一直往下挖到fib(1)所以空间复杂度O(n)。我在复习时自己画过递归树发现只要理解了系统栈是压栈再弹栈不是把整棵树同时铺开这个误区就彻底清楚了。4.3 数组的额外空间归并排序为什么整体是O(n)归并排序这里很多教材说空间复杂度O(n)但如果你只写了mergeSort的递归部分你可能觉得递归栈只有O(logn)为什么会是O(n)关键在于合并那一行merge(arr, l, mid, r)。标准归并排序的merge阶段需要额外的辅助数组来暂存两个有序子区间的元素。这个辅助数组最长会达到n因为它可能要把整个当前区间都copy到临时空间里再写回去。也就是说归并排序的空间 递归栈O(logn) 合并辅助数组O(n) O(n)。相比之下快速排序的partition是原地交换不需要大的辅助数组所以它的空间主要来自递归栈。平均情况下递归栈O(logn)最坏情况下比如上面说的退化成直链递归深度变成n空间就是O(n)。这里顺便给一个对比表方便你记忆算法最好/平均时间最坏时间平均空间最坏空间冒泡排序O(n)O(n²)O(1)O(1)选择排序O(n²)O(n²)O(1)O(1)插入排序O(n)O(n²)O(1)O(1)归并排序O(nlogn)O(nlogn)O(n)O(n)快速排序O(nlogn)O(n²)O(logn)O(n)堆排序O(nlogn)O(nlogn)O(1)O(1)二叉搜索树查找O(logn)O(n)O(logn)O(n)这个表不用背但你要能推出其中任意一行。比如堆排序空间O(1)是因为它直接在原数组上调整堆没有用额外数组二叉搜索树的查找时间取决于树高平衡树是O(logn)退化成单链表就是O(n)。5. 易错点与实战建议从看代码到写出复杂度的一条路径5.1 常见错误看到for就写O(n)、忽略每次循环里的操作我观察到一个规律刚开始学复杂度的同学特别容易形成几层for就是O(n的几次方)的肌肉记忆。这个经验对最普通的满循环有效但对很多变种会翻车。举几个翻车例子// 反例1外循环n次内循环固定100次 → 复杂度是O(100n) O(n) for (int i 0; i n; i) { for (int j 0; j 100; j) { count; } }内层j最多到100是常数循环不随n变化。总次数是100n常数100被吸收结果O(n)不是O(n²)。// 反例2每次循环做的事情不是O(1)而是O(n) for (int i 0; i n; i) { for (int j 0; j n; j) { for (int k 0; k n; k) { count; } } }三层满循环O(n³)谁都能看出来。但如果是for (int i 0; i n; i) { // 假设这里调用了一个内部要遍历n次的函数 someFunctionThatIsOn(); }外层n次每次调用O(n)的函数总复杂度O(n²)。所以分析时不要只看for还要看循环体里干了什么。如果循环体里是一个遍历链表的操作或一个排序调用整体复杂度要把它们乘进去。5.2 最坏/平均/最好要分清楚复杂度还得分最好情况最坏情况平均情况。快速排序最典型数组有序时选第一个元素当基准直接退化成O(n²)数组乱序时期望接近O(nlogn)。考试和面试里冒泡排序也常出现数组本来就排好序最好情况下只需跑一轮没有发生交换复杂度O(n)反过来完全逆序时跑满n-1轮O(n²)。所以当你被问冒泡排序时间复杂度时标准答法是最坏O(n²)最好O(n)如果加了交换标志位最好能提前结束。我个人的建议是所有复杂度回答先讲默认的那个没特别说明通常指最坏情况或平均情况再补一句什么情况下会退化。比如这个算法平均O(nlogn)但最坏会退化到O(n²)因为基准选得不好。这样回答信息量完整也能体现你真的理解这个算法而不是背了个结论。5.3 考试和面试里怎么答复杂度问题最后分享一套我复习时总结的答题顺序实测对空题、手写推导题和面试口述都适用明确规模n说清楚这里n指数组长度/链表节点数/树的节点数。找基本操作指出哪条语句最核心比如排序里的比较或交换、查找里的比较、合并里的拷贝。数次数并推导如果是循环写出求和式如果是递归写出递推式然后化简到大O。别忘了空间先看有没有额外数组再看有没有递归递归说递归深度是多少。比如面试官让你分析下面这个有序数组二分查找int binarySearch(int a[], int n, int target) { int l 0, r n - 1; while (l r) { int mid l (r - l) / 2; if (a[mid] target) return mid; else if (a[mid] target) l mid 1; else r mid - 1; } return -1; }你就可以这样答规模n是数组长度基本操作是比较a[mid]和目标值每轮把区间缩小一半最多执行log2n次比较所以时间O(logn)只用常数个变量空间O(1)。顺便还可以补一句这里mid用l (r-l)/2而不是(lr)/2是为了防止lr溢出。这就是一个非常完整的回答。再比如二叉树的中序遍历递归void inorder(struct TreeNode* root) { if (!root) return; inorder(root-left); visit(root); inorder(root-right); }规模n是树的节点数每个节点被visit一次所以时间O(n)空间是递归深度取决于树高h平衡二叉树是O(logn)最坏情况下树退化成链是O(n)。你会发现真正常考的复杂度题目翻来覆去就是这几类循环求和、递归递推、树的高度、排序的分治。把上面每个例子亲手推一遍比我当年干背那堆复杂度结论要扎实得多。我自己复习复杂度这块时最后总结成一句话**先找n再找关键操作然后数次数碰到递归时间看调用次数空间看递归深度。**这句话虽然不是万能公式但对90%的数据结构题目都够用。考试的时候能写过程就别只写答案把因为最内层循环执行了n(n-1)/2次所以冒泡排序是O(n²)这种话写上去阅卷老师想扣分都找不到理由。