考过408的人都知道数据结构书翻开的第一个“要背”的考点往往就是时间复杂度和空间复杂度。当年我刚开始复习的时候觉得这玩意儿不过就是数一下循环嵌套几层O(n²)、O(logn)记住就完了。结果做了几套统考真题才发现自己太天真了选择题考边界条件综合题考复杂度对整个算法设计的影响有些题表面上在考“排序稳定性”实际上考的是“空间复杂度为O(1)的原地排序有哪些”。这门课里复杂度分析不是孤立的小节而是贯穿链表、树、图、查找、排序所有知识点的“度量衡”。这篇内容就是专门写给正在备考408的朋友们尤其是基础阶段刚开始啃《数据结构》的。我会把时间复杂度和空间复杂度怎么理解、怎么算、怎么在真题里用掰开揉碎讲一遍再结合统考真题的常见考法帮你把这块地基打牢。不管你是跨考还是科班但基础一般只要把这一块吃透后续复习任何数据结构都会顺畅很多。1. 为什么说时间复杂度和空间复杂度是408入门的“第一关”1.1 这个考点在408真题中的地位先说个直观数据408统考数据结构部分一共有11道选择题和1-2道大题。时间复杂度和空间复杂度这个概念直接考的题可能每套卷子只有1到2道但它间接影响着大量的题目选择。比如“某排序算法在最好情况下的时间复杂度为O(n)”这种选项就是直接在考排序法的复杂度。再比如考察图的遍历、最短路径、最小生成树时经常要对比不同算法的时间复杂度像Dijkstra和Floyd的适用场景复杂度就是核心区别。至于空间复杂度几乎是“原地算法”这种概念的标配大题里让你“设计一个空间复杂度为O(1)的算法”一旦没满足整道题可能扣掉一半分。所以别看大纲里只写了“理解时间复杂度和空间复杂度”几个字实际考试里它是所有算法题目的“隐性规则”。你不能等到写代码了再去想复杂度而是在分析问题、选择数据结构、设计算法步骤的那一刻就得心里有数。1.2 新手最容易踩的坑背答案不如懂分析很多同学复习复杂度第一反应是背一张表顺序表O(1)链表O(n)快排平均O(nlogn)……背下来以后做题确实能对一部分但遇到变形题就会翻车。比如给你一段代码循环体里面有一句“if(i % 2 0) x;”问你时间复杂度是多少。如果你只会“看到双层循环就是O(n²)”那这种题你大概率会答错因为这里内层循环可能只执行一半次数。我自己的体会是复杂度不是一个“死结论”而是一种“上界估计”的思路。你不需要精确到每次语句执行多少条但你必须知道执行次数和输入规模n之间是什么关系。比如是常数次、对数次、线性次、n次方次还是阶乘次。这个能力只能靠手推代码来练不能靠背。真题里经常出现的就是“给一段代码问时间复杂度”这种题就是在逼你现场推推导而不是默写表格。1.3 复习资料与题库的选择市面上408数据结构的资料很多我复习时用的搭配是教材以严蔚敏老师的《数据结构C语言版》为主配合王道考研的《数据结构复习指导》和历年真题汇编。严蔚敏的书偏原理和数学推导适合把复杂度概念弄透彻王道则更贴近考试总结了很多口诀和题型。另外一定要准备一个错题本专门记录因为复杂度计算错误而丢分的题反复看。如果你刚开始复习建议不要一上来就去刷真题先花两到三周把复杂度分析的基本功练扎实。这部分是“一劳永逸”的投资后面学树、图、排序都会用到。还有一个小建议可以找一个复习搭子互相出代码题让对方算复杂度这种互动式学习比独自刷题记得牢。2. 时间复杂度分析的核心方法从代码到数学2.1 基本概念大O记号到底在说什么时间复杂度不是精确的运行秒数而是算法执行时间随输入规模n增长的趋势。我们用大O记号来表示这个趋势的“上界”。比如O(n)表示运行时间和n成正比O(n²)表示运行时间和n的平方成正比O(logn)表示增长很慢即使n变成一百亿实际运行次数也只有几十次。要理解大O得先知道它忽略掉了什么。它忽略系数比如运行时间是3n2和100n1都是O(n)。也忽略低阶项比如n²n1是O(n²)。所以你计算复杂度时只要抓住“大头”就行。比如一个双重循环外层n次内层平均n/2次那么总次数大约是n²/2依然是O(n²)。千万不要在这里纠结要不要写成O(0.5n²)考试里只需要写出大O即可。这里还要说一下统考选择题偶尔会考到“最坏时间复杂度”和“平均时间复杂度”的区别。比如快排平均O(nlogn)最坏O(n²)。真题会让你判断“快排最坏情况是O(n²)”对不对。所以你需要分清每个算法在最好、最坏、平均三种情况下的复杂度这是高频考点。2.2 分析循环代码的三步法拿到一段代码想要准确算复杂度我习惯用三步第一步找核心操作。也就是执行次数最多的那条语句通常出现在最内层循环体。比如循环里只有一个“x;”那就数它执行了几次。第二步确定循环变量和终止条件。看循环变量是从0开始还是从1开始条件是“i n”还是“i n”每次增量是i还是i * 2。这一步最容易出错尤其要注意边界是“”还是“”差一个常数不影响大O但差一个数量级就会错。第三步把执行次数写成关于n的表达式再化简为大O形式。如果嵌套循环就把每层次数乘起来如果循环变量步长变化可能需要解方程。举个例子这是我在真题里见过无数次的模式int i 1; while (i n) { x; i i * 2; }这里i每次翻倍循环次数k满足2^k ≤ n所以k约等于logn故时间复杂度为O(logn)。很多背了“单层循环是O(n)”的同学在这种题上就栽了。关键就是看循环变量的变化方式自增就是O(n)倍增就是O(logn)倍减有时也是O(logn)。2.3 递归算法的时间复杂度主定理与递归树递归算法的时间复杂度是408难点尤其是像快速排序、归并排序、二叉树的遍历这些。递归的时间复杂度往往由一个递推公式描述比如归并排序T(n) 2T(n/2) O(n)意思是把问题分成两个规模为n/2的子问题合并需要O(n)时间。解这个递推公式结果是O(nlogn)。我不会去硬背主定理更推荐用递归树来理解。把递归调用过程画成一棵树第一层有一个节点代价是O(n)第二层有两个节点总代价O(n)第三层四个节点总代价O(n)……每层总代价一样而有logn层所以总复杂度是O(nlogn)。换一个公式T(n) T(n/2) O(1)比如二分查找这棵树每一层只有一个节点每层代价O(1)总共logn层结果就是O(logn)。画递归树这个方法很直观建议大家在纸上多画几遍。不过要注意不是所有递归都能套主定理。比如斐波那契数列的朴素递归T(n) T(n-1) T(n-2) O(1)它的递归树两个分支不平衡总节点数是指数级的复杂度是O(2^n)。这种题常用来考“分治”和“暴力递归”的差距。2.4 经典场景排序法和数据结构的操作复杂度复杂度在排序和数据结构操作中极其重要。我复习时自己整理了“高频复杂度速查表”这里分享给大家直接插入排序最好O(n)平均O(n²)最坏O(n²)空间O(1)希尔排序平均O(n^1.3)左右最坏O(n²)空间O(1)冒泡排序最好O(n)平均O(n²)最坏O(n²)空间O(1)快速排序最好/平均O(nlogn)最坏O(n²)空间O(logn)递归栈简单选择排序最好/平均/最坏均为O(n²)空间O(1)堆排序最好/平均/最坏均为O(nlogn)空间O(1)归并排序最好/平均/最坏均为O(nlogn)空间O(n)顺序表按值查找最好O(1)最坏O(n)链表按位查找O(n)二叉排序树操作平均O(logn)最坏O(n)哈希表查找平均O(1)这些数不用死记但你要会推导。比如为什么堆排序的空间复杂度是O(1)因为它是原地调整堆不需要额外数组。而归并排序需要临时数组所以空间O(n)。真题里经常给几个排序算法让你比较空间复杂度这种题就是考察你是否清楚每个算法的实现细节。3. 空间复杂度分析没那么简单但也没那么难3.1 空间复杂度到底算的是什么空间复杂度指的是算法在运行过程中除了输入本身所占的存储空间外额外需要的辅助空间随n增长的趋势。注意“输入数据本身”的空间不算因为那是问题给的我们只算“多出来的”。比如排序算法里如果用了O(n)的辅助数组空间就是O(n)如果只用几个临时变量那空间就是O(1)。很多同学会把空间复杂度和“程序代码长短”搞混其实完全不是一回事。代码长不代表空间大代码短也不代表空间小。空间复杂度关心的是运行时的存储分配比如递归调用需要的函数栈、动态申请的数组/链表节点等。如果算法每递归一层就要申请一批新空间那递归深度就会直接影响空间复杂度。这里有一个容易忽略的点C语言里数组大小如果由参数n决定比如“int a[n];”那么这个数组占用的空间就是O(n)。而在某些考试题目里要求“空间复杂度为O(1)”那就意味着你除了少数几个变量外不能开大小为n的辅助数组也不能用递归来隐式占用O(n)栈空间。这一点在408大题中经常作为约束条件出现务必重视。3.2 递归栈空间的计算递归的空间复杂度 递归深度 × 每层开辟的临时空间。最典型的就是二叉树的前序递归遍历递归深度最坏情况下等于树的高度如果树是斜树高度为n那空间就是O(n)如果是平衡二叉树高度为logn空间就是O(logn)。这也就是为什么快排递归调用的平均空间复杂度是O(logn)而在最坏情况下每次划分极不平衡递归深度达到n空间复杂度就退化为O(n)。另外有些题目让你“把递归算法改成非递归”往往不是时间复杂度重要而是想让你把空间复杂度从O(n)降到O(1)。比如二叉树的Morris遍历就是利用了线索化的思想把空间复杂度压缩到O(1)。这个知识点在408中虽然不常单独考但在大题中可能会作为优化方向来引导你思考。计算递归空间时还有一个坑有人分不清“递归树的总节点数”和“递归深度”。时间复杂度看总节点数空间复杂度看递归深度因为栈上同时存在的帧数最多等于一条路径的深度而不是全部节点都能同时在栈里。画一棵树路上最长的分支就是递归深度。比如归并排序递归深度是logn虽然总节点数O(n)但空间复杂度只看深度和每层辅助空间归并排序的每层还需要O(n)的辅助数组这里再细分如果每层都开临时数组那么空间复杂度是O(nlogn)但标准实现一般只开一个全局临时数组每层复用所以空间复杂度是O(n)。这也是408常考的一个点归并排序的空间复杂度是O(n)而不是O(nlogn)。3.3 原地算法与额外空间技巧“原地算法”指空间复杂度为O(1)的算法只允许用常数个额外变量。真题里非常喜欢出“设计一个O(1)空间的算法”这种题尤其是在数组操作和链表操作中。比如统考真题里有一个经典题型一个顺序表L中存放着n个整数要求设计一个算法将表中所有小于0的元素放到所有大于等于0的元素前面要求时间O(n)、空间O(1)。这个题其实类似快排的划分过程用两个指针从两端向中间扫描交换不满足条件的元素就能做到O(n)时间和O(1)空间。很多人第一反应是开一个临时数组把负数放前面、非负数放后面虽然也能完成但空间复杂度O(n)不满足题目要求丢分很可惜。再比如链表逆置要求空间O(1)。这时你不能用栈来辅助而应该用三指针原地翻转节点的next指针。这类题在王道书上都是重点题型做的时候一定要先在草稿纸上画一下指针变化否则很容易绕晕。原地算法不是说不能有局部变量而是局部变量必须是有限个不能随n增长。4. 统考真题实战思路怎么用复杂度理论解题4.1 选择题中的复杂度陷阱选择题里考复杂度最常见的有三种套路第一种给一段简短代码问时间复杂度。比如题目可能会给这样的循环for (int i 1; i n; i) for (int j 1; j i; j) x;这里内层循环次数是123...n等于n(n1)/2所以复杂度是O(n²)。这种题考的是你能否识别“1到n累加”这个求和公式。第二种给一个算法或数据结构操作问你“最坏情况下”或“平均情况下”的时间复杂度。例如单链表在给定某个结点之后插入新结点已知该结点的指针时间复杂度是O(1)但如果不知道指针只给元素值需要先查找位置复杂度是O(n)。这种题就是考你对链表物理结构的理解。第三种比较几个算法的复杂度大小比如问“下列排序算法中平均时间复杂度最低的是哪个”选项有快排、冒泡、简单选择、堆排序。这里如果熟悉复杂度表一眼就能排除掉O(n²)的算法剩下快排和堆排序平均都是O(nlogn)这时候就要注意题目问的是“平均复杂度最低”还是“最稳定”不要混淆概念。我见过很多同学在这里失分就是因为没看清题目问的是“时间复杂度”还是“辅助空间”或者把“平均”看成了“最坏”。4.2 综合题中复杂度作为“最值约束”408数据结构大题特别是设计算法的那道几乎每道都有时间和空间复杂度的限制。常见的措辞是“设计一个时间上尽可能高效的算法”或“要求时间O(n)、空间O(1)”。这时候复杂度约束就直接决定了你能用什么方法。举一个高频考点在一组数据中寻找第k小的元素。如果排序再找时间O(nlogn)如果能利用快排的划分思想平均O(n)这就是快速选择算法。真题可能不会直接问“第k小”而是问“找出数组中未出现的最小正整数”你可以先使用辅助数组标记出现过的正数空间O(n)也可以用原地交换法做到空间O(1)。两种解法分数差距很大因为题目往往明确要求“空间O(1)”。所以我在做题时看到“尽可能高效”四个字就会先圈出来然后在草稿纸上先写下时间、空间复杂度的要求再设计算法。不要一上来就想着暴力解写出了暴力解再优化往往时间来不及。更好的习惯是第一遍读题就确定复杂度目标然后根据目标反推算法类别。如果要求O(logn)大概率是二分如果要求O(n)而且空间O(1)大概率是双指针、原地划分或哈希没有空间限制时如果要求O(nlogn)可以先排序再处理。4.3 真题演练示例循环边界与递归深度为了让大家更直观地看到真题怎么考我拿两个常见的真题原型来模拟一遍思路。第一个原型写出下面程序段的时间复杂度int sum 0; for (int i 1; i n; i * 2) for (int j 0; j i; j) sum;外层循环变量i是倍增的i的取值为1、2、4、...、小于n的最大2的幂。内层循环次数等于i。于是总执行次数S 1 2 4 ... 2^⌊log2(n-1)⌋这是一个等比数列结果约为2n量级所以时间复杂度是O(n)。这个题如果你看到外层是O(logn)内层是O(n)直接相乘得到O(nlogn)那就错了因为内层j的次数和外层i有关联不是独立的n。正确方式是把内层次数累加。这种“嵌套但变量关联”的结构是真题单选题最常设的陷阱。第二个原型一个递归函数如下int func(int n) { if (n 1) return 1; return func(n - 1) func(n - 1); }这个递归每次产生两个子问题每个子问题规模减1它的递推公式是T(n) 2T(n-1) O(1)最终结果是O(2^n)。递归深度其实只有n所以空间复杂度是O(n)。很多同学以为递归调用次数多空间复杂度也是指数级这是不对的因为栈空间是成一条链释放的而不是同时容纳所有调用。这种“指数时间、线性空间”的组合在选择题里出现过要特别注意。5. 备考经验与常见问题速查5.1 复习时间线建议如果你是从现在才开始准备408我建议把复杂度分析放在整个数据结构复习的最前沿用一周左右搞透。具体安排可以这样第一到第二天吃透基本概念和大O记号能把常见循环代码的复杂度化成标准形式。第三到第四天集中练习递归算法用递归树解递推公式至少做20道题。第五到第六天把常用数据结构和排序算法的复杂度整理成一张表并自己推导其中至少一半结论。第七天找一份早年的408真题或王道习题集只做关于复杂度的选择题和大题检验自己的掌握程度。注意不要急着把算法设计学到很深第一个月里你只需要做到“给代码能算复杂度给算法能描述复杂度”即可。深度优先、广度优先、图的最短路径这些具体算法复杂度等到学对应章节时再结合真题进行强化。这样安排既能保证复杂度这个基础工具提前掌握又不会因为对后续算法不熟而影响心态。5.2 常见错误Top5我结合身边研友和网上的经验总结了五个最常犯的错误第一忽略最坏情况。有些算法平均复杂度低但最坏复杂度高比如快速排序。如果题目问“所有情况下一定不慢于O(nlogn)的排序算法”你要选堆排序或归并排序而不能选快排。第二把循环里的某条语句看成常数。比如循环体内有一个调用函数的语句而这个函数本身也是O(n)复杂度那么整体可能会变成O(n²)。这种“隐藏循环”在链表操作中很常见比如在循环里调用“查找位置”的函数。第三空间复杂度漏算递归栈。凡是递归算法空间复杂度至少是递归深度。不要因为算法没有显式申请数组就认为空间是O(1)。第四把log的底数写进复杂度。数据结构和算法中log的底数不影响渐近复杂度因此不能写O(log₂n)这样精确的底数考试里标准写法是O(logn)。这个知识点偶尔会出现在判断题里。第五分不清“平均”和“最坏”。统考真题喜欢问“以下哪种说法正确”选项里会把平均复杂度说成最坏复杂度来混淆。比如插入排序的平均和最坏都是O(n²)但最好O(n)有些说法会写成“插入排序最坏O(n)”就是一种常见干扰项。5.3 真题/模拟题刷题建议刷题方面我建议“2024年以前的408历年真题”里的复杂度相关题目至少做两遍。第一遍按章节做第二遍按年份整套做。早年真题里有很多关于复杂度的经典设计题虽然年份久远但考点仍然有参考价值。除了真题王道的《数据结构》配套习题难度和风格都接近统考特别是每章后面的选择题。用这些题来训练“题干中隐含复杂度条件”的敏感度。做题时不要只把答案选出来要把每个选项都想想“如果改一下限制条件选什么”。比如题目问“顺序存储的线性表在第i个位置插入元素的时间复杂度”你把“顺序存储”改成“链式存储”答案会从O(n)变成O(1)已知结点。这样对比着练复杂度知识才记得牢。我自己还习惯把错题按“算时间复杂度误用乘法”和“空间复杂度忘记递归栈”这些错因来分类而不是按章节分类。这样一来冲刺阶段复习错题时一眼就能看到自己思维上的弱点。你也不妨试试。最后再说一点个人经验复杂度分析这个能力不是靠刷一遍题就能完全掌握的它会在你复习链表、栈队列、树、图、排序时被反复用到。一开始算得慢、算错都很正常。我在备考那会儿光是快排的时间复杂度推导就画了三大张纸。后来见的题多了慢慢就形成了一种直觉看到“二分”想到logn看到“双重循环”先判断内外层变量是否关联看到“递归”第一反应是画递归树。这种直觉是可以刻意练出来的。希望这篇内容能帮你少走些弯路把这门“基本功”稳稳拿下。后面复习过程中如果遇到具体的复杂度迷思欢迎随时来交流。
408数据结构入门：时间复杂度和空间复杂度全解析
考过408的人都知道数据结构书翻开的第一个“要背”的考点往往就是时间复杂度和空间复杂度。当年我刚开始复习的时候觉得这玩意儿不过就是数一下循环嵌套几层O(n²)、O(logn)记住就完了。结果做了几套统考真题才发现自己太天真了选择题考边界条件综合题考复杂度对整个算法设计的影响有些题表面上在考“排序稳定性”实际上考的是“空间复杂度为O(1)的原地排序有哪些”。这门课里复杂度分析不是孤立的小节而是贯穿链表、树、图、查找、排序所有知识点的“度量衡”。这篇内容就是专门写给正在备考408的朋友们尤其是基础阶段刚开始啃《数据结构》的。我会把时间复杂度和空间复杂度怎么理解、怎么算、怎么在真题里用掰开揉碎讲一遍再结合统考真题的常见考法帮你把这块地基打牢。不管你是跨考还是科班但基础一般只要把这一块吃透后续复习任何数据结构都会顺畅很多。1. 为什么说时间复杂度和空间复杂度是408入门的“第一关”1.1 这个考点在408真题中的地位先说个直观数据408统考数据结构部分一共有11道选择题和1-2道大题。时间复杂度和空间复杂度这个概念直接考的题可能每套卷子只有1到2道但它间接影响着大量的题目选择。比如“某排序算法在最好情况下的时间复杂度为O(n)”这种选项就是直接在考排序法的复杂度。再比如考察图的遍历、最短路径、最小生成树时经常要对比不同算法的时间复杂度像Dijkstra和Floyd的适用场景复杂度就是核心区别。至于空间复杂度几乎是“原地算法”这种概念的标配大题里让你“设计一个空间复杂度为O(1)的算法”一旦没满足整道题可能扣掉一半分。所以别看大纲里只写了“理解时间复杂度和空间复杂度”几个字实际考试里它是所有算法题目的“隐性规则”。你不能等到写代码了再去想复杂度而是在分析问题、选择数据结构、设计算法步骤的那一刻就得心里有数。1.2 新手最容易踩的坑背答案不如懂分析很多同学复习复杂度第一反应是背一张表顺序表O(1)链表O(n)快排平均O(nlogn)……背下来以后做题确实能对一部分但遇到变形题就会翻车。比如给你一段代码循环体里面有一句“if(i % 2 0) x;”问你时间复杂度是多少。如果你只会“看到双层循环就是O(n²)”那这种题你大概率会答错因为这里内层循环可能只执行一半次数。我自己的体会是复杂度不是一个“死结论”而是一种“上界估计”的思路。你不需要精确到每次语句执行多少条但你必须知道执行次数和输入规模n之间是什么关系。比如是常数次、对数次、线性次、n次方次还是阶乘次。这个能力只能靠手推代码来练不能靠背。真题里经常出现的就是“给一段代码问时间复杂度”这种题就是在逼你现场推推导而不是默写表格。1.3 复习资料与题库的选择市面上408数据结构的资料很多我复习时用的搭配是教材以严蔚敏老师的《数据结构C语言版》为主配合王道考研的《数据结构复习指导》和历年真题汇编。严蔚敏的书偏原理和数学推导适合把复杂度概念弄透彻王道则更贴近考试总结了很多口诀和题型。另外一定要准备一个错题本专门记录因为复杂度计算错误而丢分的题反复看。如果你刚开始复习建议不要一上来就去刷真题先花两到三周把复杂度分析的基本功练扎实。这部分是“一劳永逸”的投资后面学树、图、排序都会用到。还有一个小建议可以找一个复习搭子互相出代码题让对方算复杂度这种互动式学习比独自刷题记得牢。2. 时间复杂度分析的核心方法从代码到数学2.1 基本概念大O记号到底在说什么时间复杂度不是精确的运行秒数而是算法执行时间随输入规模n增长的趋势。我们用大O记号来表示这个趋势的“上界”。比如O(n)表示运行时间和n成正比O(n²)表示运行时间和n的平方成正比O(logn)表示增长很慢即使n变成一百亿实际运行次数也只有几十次。要理解大O得先知道它忽略掉了什么。它忽略系数比如运行时间是3n2和100n1都是O(n)。也忽略低阶项比如n²n1是O(n²)。所以你计算复杂度时只要抓住“大头”就行。比如一个双重循环外层n次内层平均n/2次那么总次数大约是n²/2依然是O(n²)。千万不要在这里纠结要不要写成O(0.5n²)考试里只需要写出大O即可。这里还要说一下统考选择题偶尔会考到“最坏时间复杂度”和“平均时间复杂度”的区别。比如快排平均O(nlogn)最坏O(n²)。真题会让你判断“快排最坏情况是O(n²)”对不对。所以你需要分清每个算法在最好、最坏、平均三种情况下的复杂度这是高频考点。2.2 分析循环代码的三步法拿到一段代码想要准确算复杂度我习惯用三步第一步找核心操作。也就是执行次数最多的那条语句通常出现在最内层循环体。比如循环里只有一个“x;”那就数它执行了几次。第二步确定循环变量和终止条件。看循环变量是从0开始还是从1开始条件是“i n”还是“i n”每次增量是i还是i * 2。这一步最容易出错尤其要注意边界是“”还是“”差一个常数不影响大O但差一个数量级就会错。第三步把执行次数写成关于n的表达式再化简为大O形式。如果嵌套循环就把每层次数乘起来如果循环变量步长变化可能需要解方程。举个例子这是我在真题里见过无数次的模式int i 1; while (i n) { x; i i * 2; }这里i每次翻倍循环次数k满足2^k ≤ n所以k约等于logn故时间复杂度为O(logn)。很多背了“单层循环是O(n)”的同学在这种题上就栽了。关键就是看循环变量的变化方式自增就是O(n)倍增就是O(logn)倍减有时也是O(logn)。2.3 递归算法的时间复杂度主定理与递归树递归算法的时间复杂度是408难点尤其是像快速排序、归并排序、二叉树的遍历这些。递归的时间复杂度往往由一个递推公式描述比如归并排序T(n) 2T(n/2) O(n)意思是把问题分成两个规模为n/2的子问题合并需要O(n)时间。解这个递推公式结果是O(nlogn)。我不会去硬背主定理更推荐用递归树来理解。把递归调用过程画成一棵树第一层有一个节点代价是O(n)第二层有两个节点总代价O(n)第三层四个节点总代价O(n)……每层总代价一样而有logn层所以总复杂度是O(nlogn)。换一个公式T(n) T(n/2) O(1)比如二分查找这棵树每一层只有一个节点每层代价O(1)总共logn层结果就是O(logn)。画递归树这个方法很直观建议大家在纸上多画几遍。不过要注意不是所有递归都能套主定理。比如斐波那契数列的朴素递归T(n) T(n-1) T(n-2) O(1)它的递归树两个分支不平衡总节点数是指数级的复杂度是O(2^n)。这种题常用来考“分治”和“暴力递归”的差距。2.4 经典场景排序法和数据结构的操作复杂度复杂度在排序和数据结构操作中极其重要。我复习时自己整理了“高频复杂度速查表”这里分享给大家直接插入排序最好O(n)平均O(n²)最坏O(n²)空间O(1)希尔排序平均O(n^1.3)左右最坏O(n²)空间O(1)冒泡排序最好O(n)平均O(n²)最坏O(n²)空间O(1)快速排序最好/平均O(nlogn)最坏O(n²)空间O(logn)递归栈简单选择排序最好/平均/最坏均为O(n²)空间O(1)堆排序最好/平均/最坏均为O(nlogn)空间O(1)归并排序最好/平均/最坏均为O(nlogn)空间O(n)顺序表按值查找最好O(1)最坏O(n)链表按位查找O(n)二叉排序树操作平均O(logn)最坏O(n)哈希表查找平均O(1)这些数不用死记但你要会推导。比如为什么堆排序的空间复杂度是O(1)因为它是原地调整堆不需要额外数组。而归并排序需要临时数组所以空间O(n)。真题里经常给几个排序算法让你比较空间复杂度这种题就是考察你是否清楚每个算法的实现细节。3. 空间复杂度分析没那么简单但也没那么难3.1 空间复杂度到底算的是什么空间复杂度指的是算法在运行过程中除了输入本身所占的存储空间外额外需要的辅助空间随n增长的趋势。注意“输入数据本身”的空间不算因为那是问题给的我们只算“多出来的”。比如排序算法里如果用了O(n)的辅助数组空间就是O(n)如果只用几个临时变量那空间就是O(1)。很多同学会把空间复杂度和“程序代码长短”搞混其实完全不是一回事。代码长不代表空间大代码短也不代表空间小。空间复杂度关心的是运行时的存储分配比如递归调用需要的函数栈、动态申请的数组/链表节点等。如果算法每递归一层就要申请一批新空间那递归深度就会直接影响空间复杂度。这里有一个容易忽略的点C语言里数组大小如果由参数n决定比如“int a[n];”那么这个数组占用的空间就是O(n)。而在某些考试题目里要求“空间复杂度为O(1)”那就意味着你除了少数几个变量外不能开大小为n的辅助数组也不能用递归来隐式占用O(n)栈空间。这一点在408大题中经常作为约束条件出现务必重视。3.2 递归栈空间的计算递归的空间复杂度 递归深度 × 每层开辟的临时空间。最典型的就是二叉树的前序递归遍历递归深度最坏情况下等于树的高度如果树是斜树高度为n那空间就是O(n)如果是平衡二叉树高度为logn空间就是O(logn)。这也就是为什么快排递归调用的平均空间复杂度是O(logn)而在最坏情况下每次划分极不平衡递归深度达到n空间复杂度就退化为O(n)。另外有些题目让你“把递归算法改成非递归”往往不是时间复杂度重要而是想让你把空间复杂度从O(n)降到O(1)。比如二叉树的Morris遍历就是利用了线索化的思想把空间复杂度压缩到O(1)。这个知识点在408中虽然不常单独考但在大题中可能会作为优化方向来引导你思考。计算递归空间时还有一个坑有人分不清“递归树的总节点数”和“递归深度”。时间复杂度看总节点数空间复杂度看递归深度因为栈上同时存在的帧数最多等于一条路径的深度而不是全部节点都能同时在栈里。画一棵树路上最长的分支就是递归深度。比如归并排序递归深度是logn虽然总节点数O(n)但空间复杂度只看深度和每层辅助空间归并排序的每层还需要O(n)的辅助数组这里再细分如果每层都开临时数组那么空间复杂度是O(nlogn)但标准实现一般只开一个全局临时数组每层复用所以空间复杂度是O(n)。这也是408常考的一个点归并排序的空间复杂度是O(n)而不是O(nlogn)。3.3 原地算法与额外空间技巧“原地算法”指空间复杂度为O(1)的算法只允许用常数个额外变量。真题里非常喜欢出“设计一个O(1)空间的算法”这种题尤其是在数组操作和链表操作中。比如统考真题里有一个经典题型一个顺序表L中存放着n个整数要求设计一个算法将表中所有小于0的元素放到所有大于等于0的元素前面要求时间O(n)、空间O(1)。这个题其实类似快排的划分过程用两个指针从两端向中间扫描交换不满足条件的元素就能做到O(n)时间和O(1)空间。很多人第一反应是开一个临时数组把负数放前面、非负数放后面虽然也能完成但空间复杂度O(n)不满足题目要求丢分很可惜。再比如链表逆置要求空间O(1)。这时你不能用栈来辅助而应该用三指针原地翻转节点的next指针。这类题在王道书上都是重点题型做的时候一定要先在草稿纸上画一下指针变化否则很容易绕晕。原地算法不是说不能有局部变量而是局部变量必须是有限个不能随n增长。4. 统考真题实战思路怎么用复杂度理论解题4.1 选择题中的复杂度陷阱选择题里考复杂度最常见的有三种套路第一种给一段简短代码问时间复杂度。比如题目可能会给这样的循环for (int i 1; i n; i) for (int j 1; j i; j) x;这里内层循环次数是123...n等于n(n1)/2所以复杂度是O(n²)。这种题考的是你能否识别“1到n累加”这个求和公式。第二种给一个算法或数据结构操作问你“最坏情况下”或“平均情况下”的时间复杂度。例如单链表在给定某个结点之后插入新结点已知该结点的指针时间复杂度是O(1)但如果不知道指针只给元素值需要先查找位置复杂度是O(n)。这种题就是考你对链表物理结构的理解。第三种比较几个算法的复杂度大小比如问“下列排序算法中平均时间复杂度最低的是哪个”选项有快排、冒泡、简单选择、堆排序。这里如果熟悉复杂度表一眼就能排除掉O(n²)的算法剩下快排和堆排序平均都是O(nlogn)这时候就要注意题目问的是“平均复杂度最低”还是“最稳定”不要混淆概念。我见过很多同学在这里失分就是因为没看清题目问的是“时间复杂度”还是“辅助空间”或者把“平均”看成了“最坏”。4.2 综合题中复杂度作为“最值约束”408数据结构大题特别是设计算法的那道几乎每道都有时间和空间复杂度的限制。常见的措辞是“设计一个时间上尽可能高效的算法”或“要求时间O(n)、空间O(1)”。这时候复杂度约束就直接决定了你能用什么方法。举一个高频考点在一组数据中寻找第k小的元素。如果排序再找时间O(nlogn)如果能利用快排的划分思想平均O(n)这就是快速选择算法。真题可能不会直接问“第k小”而是问“找出数组中未出现的最小正整数”你可以先使用辅助数组标记出现过的正数空间O(n)也可以用原地交换法做到空间O(1)。两种解法分数差距很大因为题目往往明确要求“空间O(1)”。所以我在做题时看到“尽可能高效”四个字就会先圈出来然后在草稿纸上先写下时间、空间复杂度的要求再设计算法。不要一上来就想着暴力解写出了暴力解再优化往往时间来不及。更好的习惯是第一遍读题就确定复杂度目标然后根据目标反推算法类别。如果要求O(logn)大概率是二分如果要求O(n)而且空间O(1)大概率是双指针、原地划分或哈希没有空间限制时如果要求O(nlogn)可以先排序再处理。4.3 真题演练示例循环边界与递归深度为了让大家更直观地看到真题怎么考我拿两个常见的真题原型来模拟一遍思路。第一个原型写出下面程序段的时间复杂度int sum 0; for (int i 1; i n; i * 2) for (int j 0; j i; j) sum;外层循环变量i是倍增的i的取值为1、2、4、...、小于n的最大2的幂。内层循环次数等于i。于是总执行次数S 1 2 4 ... 2^⌊log2(n-1)⌋这是一个等比数列结果约为2n量级所以时间复杂度是O(n)。这个题如果你看到外层是O(logn)内层是O(n)直接相乘得到O(nlogn)那就错了因为内层j的次数和外层i有关联不是独立的n。正确方式是把内层次数累加。这种“嵌套但变量关联”的结构是真题单选题最常设的陷阱。第二个原型一个递归函数如下int func(int n) { if (n 1) return 1; return func(n - 1) func(n - 1); }这个递归每次产生两个子问题每个子问题规模减1它的递推公式是T(n) 2T(n-1) O(1)最终结果是O(2^n)。递归深度其实只有n所以空间复杂度是O(n)。很多同学以为递归调用次数多空间复杂度也是指数级这是不对的因为栈空间是成一条链释放的而不是同时容纳所有调用。这种“指数时间、线性空间”的组合在选择题里出现过要特别注意。5. 备考经验与常见问题速查5.1 复习时间线建议如果你是从现在才开始准备408我建议把复杂度分析放在整个数据结构复习的最前沿用一周左右搞透。具体安排可以这样第一到第二天吃透基本概念和大O记号能把常见循环代码的复杂度化成标准形式。第三到第四天集中练习递归算法用递归树解递推公式至少做20道题。第五到第六天把常用数据结构和排序算法的复杂度整理成一张表并自己推导其中至少一半结论。第七天找一份早年的408真题或王道习题集只做关于复杂度的选择题和大题检验自己的掌握程度。注意不要急着把算法设计学到很深第一个月里你只需要做到“给代码能算复杂度给算法能描述复杂度”即可。深度优先、广度优先、图的最短路径这些具体算法复杂度等到学对应章节时再结合真题进行强化。这样安排既能保证复杂度这个基础工具提前掌握又不会因为对后续算法不熟而影响心态。5.2 常见错误Top5我结合身边研友和网上的经验总结了五个最常犯的错误第一忽略最坏情况。有些算法平均复杂度低但最坏复杂度高比如快速排序。如果题目问“所有情况下一定不慢于O(nlogn)的排序算法”你要选堆排序或归并排序而不能选快排。第二把循环里的某条语句看成常数。比如循环体内有一个调用函数的语句而这个函数本身也是O(n)复杂度那么整体可能会变成O(n²)。这种“隐藏循环”在链表操作中很常见比如在循环里调用“查找位置”的函数。第三空间复杂度漏算递归栈。凡是递归算法空间复杂度至少是递归深度。不要因为算法没有显式申请数组就认为空间是O(1)。第四把log的底数写进复杂度。数据结构和算法中log的底数不影响渐近复杂度因此不能写O(log₂n)这样精确的底数考试里标准写法是O(logn)。这个知识点偶尔会出现在判断题里。第五分不清“平均”和“最坏”。统考真题喜欢问“以下哪种说法正确”选项里会把平均复杂度说成最坏复杂度来混淆。比如插入排序的平均和最坏都是O(n²)但最好O(n)有些说法会写成“插入排序最坏O(n)”就是一种常见干扰项。5.3 真题/模拟题刷题建议刷题方面我建议“2024年以前的408历年真题”里的复杂度相关题目至少做两遍。第一遍按章节做第二遍按年份整套做。早年真题里有很多关于复杂度的经典设计题虽然年份久远但考点仍然有参考价值。除了真题王道的《数据结构》配套习题难度和风格都接近统考特别是每章后面的选择题。用这些题来训练“题干中隐含复杂度条件”的敏感度。做题时不要只把答案选出来要把每个选项都想想“如果改一下限制条件选什么”。比如题目问“顺序存储的线性表在第i个位置插入元素的时间复杂度”你把“顺序存储”改成“链式存储”答案会从O(n)变成O(1)已知结点。这样对比着练复杂度知识才记得牢。我自己还习惯把错题按“算时间复杂度误用乘法”和“空间复杂度忘记递归栈”这些错因来分类而不是按章节分类。这样一来冲刺阶段复习错题时一眼就能看到自己思维上的弱点。你也不妨试试。最后再说一点个人经验复杂度分析这个能力不是靠刷一遍题就能完全掌握的它会在你复习链表、栈队列、树、图、排序时被反复用到。一开始算得慢、算错都很正常。我在备考那会儿光是快排的时间复杂度推导就画了三大张纸。后来见的题多了慢慢就形成了一种直觉看到“二分”想到logn看到“双重循环”先判断内外层变量是否关联看到“递归”第一反应是画递归树。这种直觉是可以刻意练出来的。希望这篇内容能帮你少走些弯路把这门“基本功”稳稳拿下。后面复习过程中如果遇到具体的复杂度迷思欢迎随时来交流。
