很多考生第一次翻开408数据结构真题信心满满去做选择题第一题结果被一段看似简单的循环卡住了。这个点就是时间复杂度。别以为它只是第一章的基础概念它在408里的地位比大多数同学想象的重要得多直接考间接也考。把时间复杂度和空间复杂度真正吃透不只是为了那1到2分的选择题而是为了后续排序、查找、树、图的所有复杂度结论不再靠死记硬背。这篇复习笔记不是教材的复述而是我结合统考真题的考法整理的一套分析套路刚起步的一轮复习适用考前打补丁同样适用。1. 先说考情复杂度在408里到底怎么考、占多少分先聊一个很多同学容易误判的问题408数据结构一共45分左右选择题有11道前几道几乎年年都在考“一段小程序的时间复杂度是多少”或者“某个算法的空间复杂度是多少”。这不是偶然而是命题组刻意安排的送分题和拉分题并存的位置。说送分是因为只要掌握分析方法这类题的套路非常固定属于必须拿下的分数。说拉分是因为命题人会通过“看着像二层循环实际是一层”“看着像O(n²)实际是O(n)”这类变形把没真正理解复杂度本质的同学筛出去。我在复习时统计过近十几年的真题里第一章直接出选择题的概率非常高而且经常出现需要动笔推导的题目光靠猜选项过不了关。更关键的是间接考。排序章节里快排、堆排、归并的时空复杂度对比是选择题的常客图章节里Dijkstra、Floyd、Prim、Kruskal的复杂度要背树章节里平衡二叉树、二叉排序树的查找复杂度也要理解。这些结论如果孤立背诵不仅容易混而且一旦题目换个问法就懵了。背后的根源就是第一章的复杂度分析没学透。所以我对408复习的第一个建议从来都是第一章不要赶进度把这个地基夯结实后面每一章都能省力气。复习目标也分两层。第一层是“给代码会算”拿到一段C语言程序能准确说出时间复杂度和空间复杂度的数量级。第二层是“给结论会解释”考到快排为什么平均O(nlog₂n)、最坏O(n²)空间为什么平均O(log₂n)时能用自己的话讲清楚。达到第二层考场上基本不会在复杂度上丢分。2. 时间复杂度计算的三板斧数次数、看循环、拆递归2.1 先把大O记号的定义说透很多同学背了“忽略常数、保留最高阶项”的口诀但不知道大O的严格含义遇到稍微变形的题目就会出错。大O记号的数学定义是存在正常数c和n₀当n≥n₀时总有T(n)≤c·f(n)则称T(n)O(f(n))。通俗理解就是当问题规模n足够大以后算法的时间开销T(n)不会超过某个常数倍的f(n)。所以大O表达的是“增长趋势的上界”不关心系数不关心低阶项只关心n变大时谁涨得快。举个例子T(n)3n²5n100大O是O(n²)。因为n很大时3n²把5n和100远远甩在后面常数3在“存在一个c”面前没有意义。这个思想贯穿所有复杂度分析后面所有的“忽略”都源于此。408默认分析的通常是最坏情况下的时间复杂度。原因很实际有些算法的耗时跟输入数据有关比如快排对有序数组反而慢考试要求算法的性能有“保证”所以研究最坏情况最稳妥。题目里没特别说明时默认就按最坏情况处理。常见复杂度按增长速度从低到高排O(1)O(log₂n)O(n)O(nlog₂n)O(n²)O(n³)O(2ⁿ)O(n!)。这个顺序要刻在脑子里。后面做选择题时经常需要判断两个复杂度谁更大比如O(nlog₂n)和O(n√n)比谁增长快这种比较本质上就是在比增长速度不是比纸面写法。2.2 循环结构的执行次数怎么数设执行t次看变量变化时间复杂度计算的核心只有一个数清楚基本操作执行了多少次。基本操作一般是赋值、比较、算术运算这些最内层的语句它们执行的次数就是T(n)。单层循环最基础。这段代码for (i 0; i n; i) { sum i; }循环体执行n次T(n)O(n)。i 2时执行n/2次O(n)不变因为系数忽略。真正容易翻车的是变量按倍数增长的循环x 2; while (x n / 2) { x x * 2; }这种题不能靠肉眼猜设执行t次。初始x2每执行一次x翻倍第t次循环结束后x2^(t1)。循环退出的条件是x≥n/2所以2^(t1)≥n/2解得t≈log₂(n/4)log₂n-2。循环执行次数是O(log₂n)量级。这道变形题在真题里出现过很多同学凭感觉选O(n)就是没有老老实实设t次推导。两层循环要看内外层关系。先看最基础的内外层独立for (i 0; i n; i) { for (j 0; j n; j) { sum; } }内层执行n次外层也n次总次数n²O(n²)。内层依赖外层时要用求和式for (i 1; i n; i) { for (j 1; j i; j) { sum; } }第i次外层循环时内层执行i次总次数12…nn(n1)/2数量级O(n²)。这里要注意虽然比n²差一个系数1/2但系数可以忽略答案还是O(n²)。还有一个非常经典的“看似O(nlog₂n)实为O(n)”陷阱for (i n; i 1; i / 2) { for (j 0; j i; j) { sum; } }外层i从n开始不断除以2内层j从0到i。总执行次数n n/2 n/4 … 1≈2n这是等比数列求和收敛于2n所以时间复杂度是O(n)不是O(nlog₂n)。为什么很多同学错选O(nlog₂n)因为他们把外层“分了log₂n趟”和内层“每趟n次”直接相乘忽略了内层的i是不断缩小的。这类题在408里是很好的区分度题目。2.3 递归函数展开递推式别被代码唬住递归函数的时间复杂度不能直接数代码行数要列递推式。最经典的一类int fact(int n) { if (n 1) return 1; return n * fact(n - 1); }设T(n)是fact(n)的时间复杂度。递归调用fact(n-1)需要T(n-1)加上本身做一次乘法和一次比较的常数时间O(1)所以T(n)T(n-1)O(1)。展开T(n)T(n-2)O(1)O(1)…T(1)n·O(1)O(n)。逻辑很清晰递归n层每层做常数时间操作总时间线性。二分查找模型的递归长这样int binarySearch(int a[], int l, int r, int key) { if (l r) return -1; int mid (l r) / 2; if (a[mid] key) return mid; if (key a[mid]) return binarySearch(a, l, mid - 1, key); else return binarySearch(a, mid 1, r, key); }每次递归只剩一半规模T(n)T(n/2)O(1)。展开T(n)T(n/2)1T(n/4)11…需要log₂n层T(n)O(log₂n)。归并排序模型的递归是T(n)2T(n/2)O(n)。含义是把问题分成两个n/2规模的子问题分别解决需要2T(n/2)合并两个有序序列需要线性时间O(n)。手动展开看规律T(n)2T(n/2)n4T(n/4)2n8T(n/8)3n…到第k层时是2^k·T(n/2^k)k·n。当n/2^k1即klog₂nT(n)n·T(1)nlog₂nO(nlog₂n)。最容易让新手懵的是朴素斐波那契递归int Fib(int n) { if (n 2) return n; return Fib(n - 1) Fib(n - 2); }这题递推式是T(n)T(n-1)T(n-2)O(1)。注意这不是2T(n/2)而是两个规模接近n的子问题。粗略估算T(n)2T(n-2)继续展开T(n)2²T(n-4)…2^(n/2)至少是O(2^(n/2))量级。严格一点算这个递推式的解是O(2ⁿ)级。考试只需要知道指数级爆炸即可。这也是为什么实际工程里不会用这种朴素递归算斐波那契——n稍微大一点就等不出来了。递归的时间复杂度分析说到底就是“数递归树的节点数”和“数递归深度”这两件事。节点数对应时间复杂度深度对应后面要讲的空间复杂度这个区分非常关键。3. 空间复杂度辅助空间和递归栈才是命题人盯着的点3.1 空间复杂度数的是“额外空间”不是输入本身空间复杂度衡量的是算法运行时需要的额外内存开销输入数据本身占的空间不算。为什么不算因为输入数据本来就要存在不算算法的“开销”。真正要算的是算法为了执行而额外开辟的变量、数组、指针、递归栈帧等。举例要把数组a[0..n-1]逆置常规写法for (i 0; i n / 2; i) { temp a[i]; a[i] a[n - 1 - i]; a[n - 1 - i] temp; }整段代码只额外开了一个变量temp连数组本身都不用重新申请空间复杂度O(1)。这种只用了常数个辅助单元的算法在408里叫“原地工作”这个术语经常在题目选项里出现看到它就直接对应S(n)O(1)。反过来归并排序为什么空间复杂度是O(n)因为合并两个有序子序列时需要一个大小和原数组相当的辅助数组来暂存元素。这个辅助数组是算法运行时额外申请的随着n线性增长所以归并排序S(n)O(n)。这个结论不需要背现场能说出“合并要用辅助数组”这一句就永远不会忘。有一种考法会故意混淆把输入数组占了n个空间说成空间复杂度O(n)。这不对。只要算法没有额外申请随n增长的辅助存储空间复杂度就是O(1)。但反过来也要注意有些算法确实额外申请了大小为n的数组比如计数排序需要计数数组这时就是O(n)或O(nk)k是数据范围。3.2 递归的空间复杂度看的是递归深度不是递归调用总次数这是大家最容易踩的坑。递归的空间复杂度取决于递归栈的最大深度也就是同时存在多少个函数调用帧而不是整个递归过程一共调用了多少次。看前面fact(n)的例子。虽然整个递归过程要一层层调用下去再一层层返回但在最深层栈上同时有fact(n)、fact(n-1)、…、fact(1)这些帧一共n层。所以空间复杂度O(n)。用4个字的总结递归深度n。回到朴素斐波那契int Fib(int n) { if (n 2) return n; return Fib(n - 1) Fib(n - 2); }这个函数的时间复杂度是O(2ⁿ)但空间复杂度只有O(n)。为什么因为递归是深度优先执行的先一路走Fib(n-1)→Fib(n-2)→…走到最底层再回溯算另一枝同一时刻栈上的帧数最多就是递归树的高度n不是节点总数2ⁿ。很多同学看到时间复杂度O(2ⁿ)就顺手把空间复杂度也写O(2ⁿ)错了。一字之差考查的正是对递归执行过程的理解。再对比快排和归并。快速排序平均情况递归深度O(log₂n)最坏情况比如每次划分都极端不平衡递归深度O(n)所以空间复杂度平均O(log₂n)、最坏O(n)。归并排序虽然也有递归但它真正占空间的不是栈帧而是辅助数组所以空间复杂度O(n)。好好体会这个差别快排是栈深度主导归并是辅助数组主导。3.3 排序算法时空复杂度对照表这部分是408的高频考点也是“排序法时间复杂度怎么算”问得最多的原因。把八种排序的时空复杂度整理成一张表复习时反复对照排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定直接插入O(n²)O(n²)O(1)稳定希尔约O(n^1.3)O(n²)O(1)不稳定冒泡O(n²)O(n²)O(1)稳定快速O(nlog₂n)O(n²)O(log₂n)不稳定简单选择O(n²)O(n²)O(1)不稳定堆排序O(nlog₂n)O(nlog₂n)O(1)不稳定归并O(nlog₂n)O(nlog₂n)O(n)稳定基数O(d(nr))O(d(nr))O(r)稳定我复习时的记忆技巧是不稳定派——希尔、快排、简单选择、堆谐音“快些选堆”其余稳定。空间复杂度一句话串起来只有快排平均需要O(log₂n)栈空间只有归并需要O(n)辅助空间其余基本都是O(1)。时间上快排平均最快但最坏退化到O(n²)堆排和归并时间稳定在O(nlog₂n)。这张表拿住选择题的排序部分就稳了一半。4. 统考真题走一遍三道有代表性的题目拆到答案4.1 2018年真题while循环内的变量翻倍真题原题大意是这样的设n是问题规模下面程序段的时间复杂度是x 2; while (x n / 2) { x 2 * x; }选项里会有O(√n)、O(n)、O(log₂n)、O(n²)之类的干扰项。这类题的完整分析流程分三步。第一步找基本操作。这里基本操作就是x2*x它执行多少次决定了整个程序的时间复杂度。第二步设执行次数t。初始x2每执行一次x翻倍第t次执行后x2^(t1)这个表达式要写对。很多同学写成2^t差了一个因子后续推导会差出一个常数虽然不影响数量级但推导过程不严谨容易心里没底。第三步列终止条件。循环条件xn/2当x≥n/2时退出。于是2^(t1)≥n/2解t1≥log₂(n/2)t≥log₂n-2。所以执行次数是log₂n量级选O(log₂n)。这道题是典型的“看着像基础题其实考你推不推公式”。不设t凭感觉猜很容易被O(√n)这种居中选项带走。设了t90秒内一定做对。4.2 递归程序题fact(n)的时空复杂度真题里递归程序考得也很多最常见的一种int func(int n) { if (n 1) return 1; return n * func(n - 1); }两个小问通常串在一起时间复杂度和空间复杂度分别是多少答案时间复杂度O(n)空间复杂度O(n)。推导前面已经做过T(n)T(n-1)O(1)线性递推O(n)。空间上一共递归n层栈帧O(n)。这题如果写成返回func(n-1)func(n-1)就是另一道题了复杂度直接变成O(2ⁿ)。命题人常用“只改一个加号”来区分考生是否真正理解了递归模型做题时一定看清递归函数内部是几次调用。4.3 嵌套循环题内层随外层变化的等比模型再看一种经常出现在试卷前几题的二层循环模式sum 0; for (i n; i 1; i / 2) { for (j 0; j i; j) { sum; } }内层总执行次数i的第一次值n加第二次值n/2加第三次n/4一直加到1。等比数列求和收敛于2n。所以时间复杂度是O(n)不是O(nlog₂n)。真题如果给四个选项一定会有O(nlog₂n)当干扰项。这类题的通用解法是别直接“外层趟数乘内层次数”先写总执行次数的求和式再判断它是等差、等比还是乘积。每一趟内层次数固定不变才是乘法内层次数不断缩小往往是等比收敛于常数倍的首项。三道题走下来你会发现408的时间复杂度题几乎没有超出“单层循环变化规律”“二层循环求和”“递归递推式”这三种模型。把这三板斧练熟选择题前两题基本就是稳定得分。5. 易错点清单与考前背诵版5.1 高频易错点逐个排雷第一个易错点是把“最坏情况”和“平均情况”搞混。比如快排平均O(nlog₂n)最坏O(n²)两个都要记住题目问什么答什么。有些选择题挖坑就是问“快速排序在最坏情况下的时间复杂度”错误项里放O(nlog₂n)当诱饵。第二个易错点是递归树的“总节点数”和“高度”混淆。时间复杂度看总节点数——越多的子问题意味着越多计算量空间复杂度看高度——栈上同时存在的帧数只跟最深路径有关。斐波那契朴素递归的O(2ⁿ)和O(n)就是最典型的对照题。第三个易错点是log的底数无所谓。log₂n、log₁₀n在渐近复杂度里没有区别因为换底只差一个常数系数大O会忽略。所以选项里写logn、log₂n、log₃n只要底数是大于1的常数都看成同一数量级。第四个易错点是“差1不影响数量级”但推导不能差。循环i从1到n和从0到n-1执行次数都是nO(n)没跑。但while条件里是n还是≤n会导致执行次数差1不影响数量级可推导过程如果只靠数数很容易把自己绕晕。正确做法是设t次后变量等于什么再列不等式解t。第五个易错点是空间复杂度漏算递归栈。有些同学把归并排序的空间复杂度写成O(n)没问题但问快速排序的空间复杂度时他们也会写O(n)这就错了。快排需要的辅助空间就是递归栈平均O(log₂n)、最坏O(n)。问“快速排序是所有排序中平均性能最好的为什么不是O(1)空间”答案就是递归栈。5.2 考前背诵清单考前一晚或进考场前这几条必须过一遍复杂度增长速度排序O(1)O(log₂n)O(n)O(nlog₂n)O(n²)O(n³)O(2ⁿ)O(n!)二分查找复杂度时间O(log₂n)空间O(1)迭代版快排平均时间O(nlog₂n)最坏O(n²)最坏发生在基本有序/每次划分极端不平衡时空间平均O(log₂n)堆排时间O(nlog₂n)空间O(1)归并时间O(nlog₂n)空间O(n)朴素递归斐波那契时间O(2ⁿ)空间O(n)原地工作额外空间O(1)一重循环看变量变化二重循环先列求和式递归先列递推式再展开数据结构层面的操作复杂度也顺手过一遍顺序表随机访问O(1)链表按位查找O(n)哈希表平均O(1)二叉排序树平均O(log₂n)但最坏O(n)平衡二叉树保证O(log₂n)。这些常和“查找/排序算法对比”的题混在一起考。我复习到最后阶段的一个习惯是每学完一个数据结构或算法就在笔记本的固定一页写下它的时间复杂度和空间复杂度以及“为什么是这个复杂度”的一句话理由。冲刺期只看那一页效率比自己重新翻书高很多。408的复杂度题本质上考的从来不是记忆力而是“这个复杂度是怎么来的”这一层理解。把这层理解建立起来无论命题人怎么换代码、换数据结构你都能稳稳接住。