很多初学者做《算法设计与分析》第二章的习题时最大的感受往往是“上课听懂了做题却发懵”。尤其是习题2.2这类聚焦渐近记号与递归式求解的题目表面上是几道数学推导实际上却是在考察你有没有建立“规模增长直觉”。这篇文章梳理一下这类习题的核心思路、常见卡点以及我在反复批改和做题中总结出的一些实操经验。先说一个我观察到的普遍现象大家背得住大O的定义会用主定理套公式但一旦题目稍微变形——比如让你比较两个长得差不多的对数表达式、或者用递归树去解一个非标准递归式——就不知道从哪里下手。这对不上“算法设计与分析”这门课的真实要求它考的不是记忆而是你在面对未知复杂度形态时的判断力和形式化能力。习题2.2不同教材编号可能略有差异但主题通常集中在渐近分析与递归式求解上正是这样一个训练点。它要求你能够熟练证明渐近关系、对函数增长率排序、通过递归树与代换法求解递归式并且对主定理的边界情况保持敏感。这些能力不只在考试有用在后来的算法调研、系统设计评估中同样至关重要。1. 渐近记号证明别靠直觉靠定义1.1 为什么你会把“存在常数c”理解成“任意常数c”很多人做习题2.2的第一类证明题时会犯一个非常典型的错误证明 ( f(n) O(g(n)) ) 时想当然地写“因为 ( f(n) \le c \cdot g(n) ) 对所有 n 成立”但既没有说明 c 是多少也没有交代 n0 在哪里。这本质上是没有吃透 Big-O 的定义结构。大O的定义是若存在正常数 c 和 n0使得对所有 ( n \ge n0 )有 ( 0 \le f(n) \le c \cdot g(n) )则 ( f(n) O(g(n)) )。注意这里的关键词是“存在”不是“任意”。你不需要找到最好的常数只要构造出一组合法的 c 和 n0 就能完成证明。实际操作中我建议大家形成一套固定的解题动作。第一步把目标写下来。明确你要证明的是 ( f O(g) )、( f \Omega(g) ) 还是 ( f \Theta(g) )。一个很实用的技巧是拿到题目先判断 ( f/g ) 的极限趋势。如果 ( \lim_{n \to \infty} f(n)/g(n) 0 )那说明 ( f O(g) ) 但没有 ( \Omega )如果极限是常数 ( c 0 )那说明 ( f \Theta(g) )如果极限是无穷大那说明 ( f \Omega(g) )。这个极限判断法虽然不是严格证明的全部但它能告诉你证明方向对不对避免在一个错误的命题上耗时。第二步用定义写构造。假设目标是证明 ( f O(g) )你只需要做两件事找一个合适的 c找一个合适的 n0。比如要证明 ( 3n^2 2n \le c \cdot n^2 ) 对于足够大的 n 成立可以放大因为 ( 2n \le 2n^2 ) 对所有 ( n \ge 1 ) 成立所以 ( 3n^2 2n \le 5n^2 )。于是选择 c 5、n0 1证明完成。这里我想强调一个被很多人忽略的细节放大的目标不是“恰好等于”而是“可控”。只要放大后的表达式仍然是目标函数的常数倍并且只对足够大的 n 有效就可以了。不要追求最优常数追求的是“存在性”。1.2 一套可复用的解题模板附过程分析结合习题2.2中常见的题目形式我把渐近记号的证明流程拆成下面这个模板我自己在带学生和实际做题时都用这套逻辑。假设题目给出 ( f(n) 6n^3 \log n 100n^2 5 )要求证明 ( f(n) O(n^4) )。解题过程可以这样组织先设定目标对于所有 ( n \ge n0 )需要满足 ( f(n) \le c \cdot n^4 )。对每一项做放大处理。第一项 ( 6n^3 \log n )因为 ( \log n \le n ) 对所有 ( n \ge 1 ) 成立所以 ( 6n^3 \log n \le 6n^4 )。第二项 ( 100n^2 )因为 ( n^2 \le n^4 ) 对所有 ( n \ge 1 ) 成立所以 ( 100n^2 \le 100n^4 )。第三项常数 5同样 ( 5 \le 5n^4 ) 对所有 ( n \ge 1 ) 成立。把三者合并( f(n) \le (6 100 5)n^4 111n^4 )。所以取 ( c 111 )、( n0 1 ) 即可。你可能会觉得这个放大幅度太大常数 111 太难看。但在 Big-O 的体系里这完全合法。反过来说如果你在考试中写了一个很紧的 c 却算错了反而得不偿失。我见过不少同学喜欢在 c 的取值上反复打磨最后证明过程出错这是典型的“捡了芝麻丢西瓜”。还有一个高频问题什么时候用反证法当题目要求你证明“不存在这样的 c 和 n0”时比如证明 ( n^3 \neq O(n^2) )。这时候可以从反设出发假设存在常数 c 和 n0使得所有 ( n \ge n0 ) 满足 ( n^3 \le c n^2 )。那么两边同时除以 ( n^2 )得到 ( n \le c ) 对所有 ( n \ge n0 ) 成立。但这是荒谬的因为取 ( n \max(n0, \lceil c \rceil 1) ) 时( n c )矛盾。所以假设不成立。这个“取一个足够大的 n 来制造矛盾”的手法是渐近证明里最常用的反证技巧非常值得多练几次。2. 增长率排序题真正考的是“比较整数增长率”的系统方法2.1 为什么光靠直觉排序总是差那么一点习题2.2里几乎必然会出现一组函数让你按渐近增长率排序比如 ( n \log n )、( n^2 )、( 2^n )、( n! )、( n^{\lg n} ) 之类。第一次做这类题的人往往凭感觉排一个大概的次序结果总是会有个别函数排错。问题出在哪因为你在用主观经验替代系统比较。增长率的比较不是靠“看起来谁大”而是靠极限比值的判断如果 ( \lim f/g 0 )则 f 增长慢于 g如果是常数则同阶如果是无穷大则 f 增长快于 g。这个极限比值是一个完备的排序依据它把任意两个函数之间的关系都定义清楚了。对于一些难以直接求极限的形式有一个很有效的操作取对数。因为对数函数是单调递增的所以取对数不会改变增长率大小关系。把一个函数的 log 和另一个函数的 log 比较往往能把指数、阶乘这类复杂形式转换成可处理的形式。举个例子。( n! ) 和 ( 2^n ) 谁增长快直接比较不好看。取对数之后( \log(n!) \sum_{k1}^n \log k \approx n \log n )而 ( \log(2^n) n )。直观上 ( n \log n ) 明显大于 ( n )所以 ( n! ) 增长更快。更严格一点可以用斯特林公式Stirlings approximation来证明。2.2 常见函数族的分层记忆框架我不太建议死记硬背一个固定的函数排名列表因为习题往往会在函数上做变形。但有一个相对稳定的“分层框架”可以帮你快速定位任何一个函数的大致区间。层级典型函数记忆要点亚对数层( \log \log n )、( \log^* n )增长极其缓慢几乎“原地踏步”对数层( \log n )任何正次幂 ( \log^c n ) 都低于任何多项式多项式层( n^{1/2} )、( n )、( n^2 )、( n^3 )指数越大增长越快但对数与常数次幂可跨界对数多项式混合层( n \log n )、( n^2 \log n )多项式是主导项对数只是“乘数”指数层( 2^n )、( a^n )( a b ) 时 ( a^n ) 严格快于 ( b^n )阶乘与超指数层( n! )、( n^n )阶乘介于 ( c^n ) 和 ( n^n ) 之间这个表最重要的信息是( \log^c n O(n^\epsilon) ) 对所有 ( c \ge 1 )、( \epsilon 0 ) 成立以及对数函数的一个无底洞式增长。很多排序错误都出在这个核心关系上。举个例子假设让你比较 ( n \log n )、( n^{1.1} )、( n \log^{10} n ) 这三个函数的增长率。直觉上 ( n^{1.1} ) 是多项式多项式比任何对数多项式增长都快所以 ( n^{1.1} ) 最快。剩下的 ( n \log n ) 和 ( n \log^{10} n )主导项都是 n但 log 的幂次不同所以 ( n \log^{10} n ) 快于 ( n \log n )。最终排序( n \log n n \log^{10} n n^{1.1} )。很多人会栽在最后这一步他们认为 ( n \log n ) 和 ( n \log^{10} n ) 的差距是“常数因子”级别的可以忽略。这是错的log 的幂次差异在 n 增大时会累积成非常可观的差距只是它仍然不够快打不过 ( n^{1.1} ) 这种“多项式提升”。3. 从循环到递归树重走递归式求解的四条路线3.1 递归式的视角转换习题2.2中递归式求解通常会涉及 ( T(n) aT(n/b) f(n) ) 形式。但光背主定理公式只对标准形态有效。一旦系数不满足约定条件或者 f(n) 不是标准多项式就需要回到更本质的方法。我的建议是先把递归式理解成一个递归树。每一个递归调用就是树中的一个节点节点的“代价”是这一层子问题拆分时产生的非递归开销 f(n)。你要求的总复杂度最终就是所有节点代价之和。例如对于 ( T(n) 2T(n/2) n )递归树的根节点代价是 n第二层有两个节点每个代价是 n/2合计 n依此类推。每层合计都是 n而树的层数是 ( \log n )所以总代价是 ( n \log n )。又如 ( T(n) 4T(n/2) n )根节点代价 n下一层4个节点每个代价 n/2合计 2n再下一层16个节点每个代价 n/4合计 4n。每层代价翻倍而层数仍然是 ( \log n )所以总代价是等比级数 ( n(1 2 4 \dots 2^{\log n}) O(n^2) )。这个“树层代价”的观察方式比机械套主定理更可靠因为你在推算过程中能真正看到复杂度的来源。3.2 主定理的边界陷阱主定理的三种情况对应递归树中“成本主要集中在上层叶层、均匀分布、还是集中在根层”的三种格局。核心判断依据是 ( f(n) ) 与 ( n^{\log_b a} ) 的相对增长率如果 ( f(n) ) 多项式地小于后者就是叶子主导的情况复杂度由叶节点数决定如果两者同阶则每一层代价相当乘上 ( \log n )如果 ( f(n) ) 多项式地大于后者则根节点主导复杂度就是 f(n)。但主定理有一个常被忽略的适用范围在第三种情况下还需要一个额外的正则性条件也就是存在常数 ( c 1 )使得 ( a f(n/b) \le c f(n) ) 在 n 足够大时成立。很多教材里的题目故意在第三种情况设置障碍让你发现主定理无法得出结果。遇到这种局面我的建议是不要死磕主定理转用代换法也就是“猜测解 归纳证明”。这种方法看起来笨但覆盖面广。代换法的关键步骤是先用递归树或直觉猜一个复杂度上界。比如 ( T(n) 2T(n/2) n\log n )你可以猜 ( T(n) O(n \log^2 n) )。用数学归纳法验证。假设 ( T(k) \le d k \log^2 k ) 对所有 ( k n ) 成立代入递归式得到 ( T(n) \le 2d(n/2)\log^2(n/2) n\log n ) ( dn[\log n - 1]^2 n\log n ) ( dn(\log^2 n - 2\log n 1) n\log n ) ( dn\log^2 n - 2dn\log n dn n\log n ) 要想让这个结果 (\le dn\log^2 n)需要后续的项加起来不大于0即需要 ( dn n\log n \le 2dn\log n )。当 d 取足够大的常数时比如 d 2这个不等式对所有 ( n \ge 4 ) 成立。注意“足够大的常数 d”是代换法修正猜解时最常用的手段。如果你发现猜 ( O(n\log n) ) 证不出来通常不是思路错了而是差距的“常数部分”会随时间层数的累积而叠加所以猜解时记得留出额外的一个 ( \log n )。3.3 一道典型递进题的完整展开序列为了把上面的路线串起来我模拟一道习题2.2风格的递归式题目并完整走一遍题目求解 ( T(n) 3T(n/4) n^2 ) 的渐近紧确界假设 ( T(1) O(1) )。第一步识别形态。( a 3 )、( b 4 )、( f(n) n^2 )。计算 ( \log_b a \log_4 3 \approx 0.7925 )。然后比较 ( f(n) n^2 ) 和 ( n^{0.7925} )。显然 ( n^2 / n^{0.7925} n^{1.2075} \rightarrow \infty )说明 f(n) 多项式地大于叶层代价所以主定理的第三种情况可能适用。第二步检查正则条件。需要 ( a f(n/b) \le c f(n) )即 ( 3 \cdot (n/4)^2 \le c n^2 )化简得 ( \frac{3}{16} n^2 \le c n^2 )。选择 ( c 3/16 )它严格小于1所以正则条件成立。第三步下结论。由主定理第三种情况( T(n) \Theta(f(n)) \Theta(n^2) )。这道题如果换成 ( T(n) 4T(n/2) n^2 )就变成了一个经典的反例。此时 ( \log_2 4 2 )而 f(n) 同样是 ( n^2 )它们同阶命中的是主定理第二种情况结果是 ( \Theta(n^2 \log n) )而不是 ( \Theta(n^2) )。这两道题放在一起做能有效区分“第三种情况”和“第二种情况”的分界。我在实际做题中还会做一步额外验证用数学归纳法确认 ( T(n) O(n^2) ) 和 ( T(n) \Omega(n^2) ) 两边都成立。上界很容易下界需要说明递归式中每一层至少产生 f(n) 的代价所以总代价不小于根节点的 ( n^2 )。这种“一题三解”主定理、归纳、直觉验证的练习方式对加深理解非常有帮助强烈推荐用在这种习题上。4. 证明题书写规范与采分逻辑4.1 你写的是“推导”不是“说明”在习题2.2的证明题里很多同学丢分不是因为不会做而是因为“写得像答案说明”而不是“推导”。这两者的区别在于说明是在陈述结论推导是在展示结论从定义出发必然成立的过程。一个最简单的例子证明 ( f(n) 2n 10 O(n) )。错误写法因为 2n 10 的增长速度主要看 2n所以它是 O(n)。这个写法在逻辑上是跳跃的它没有引用定义更谈不上构造。规范写法取 c 12n0 10那么对所有 ( n \ge n0 )有 ( 2n 10 \le 12n )所以根据 Big-O 定义( 2n 10 O(n) )。你看差别就在于“取 c、取 n0、代入验证”这三步是完整呈现的。4.2 变量命名与量化顺序细节决定成败渐近证明中一个特别容易丢分的技术细节是量词的顺序。存在性的 c 和 n0 在前面它们的位置不是随意的。你必须在开头就声明“我取 c ...、n0 ...”然后再开始不等式推导。如果你一开始就写“对任意 ( n \ge n0 )”但又没有说明 n0 是什么这个变量就是未定义的后面的推导全部无效。还有一个常见问题是“n 的约束方向”。比如你在证明 ( 2n 10 \le 12n ) 时推导过程是 ( 10 \le 10n )这需要 ( n \ge 1 )。所以 n0 至少要是 1。但如果题目中给出初始条件 ( T(1) 1 )证明是从 ( n 1 ) 开始吗不一定。递归式归纳证明时基础情况可能需要你另外验证若干个小 n因为递归树上可能有多个节点。我建议在正式书写前做一个快速检查确认 n0 同时满足你推导中所有放缩步骤的前提。另外在证明 O 上界和 Ω 下界时很多同学只用 Big-O 记号导致结论无法“紧”。习题2.2往往要求你证明 ( \Theta ) 关系这就意味着你必须分别证明上下界。上界一般用放大法下界一般用缩小法或者直接利用递归非负的前提两者缺一不可。4.3 从批改视角看采分点分布这里分享一些我在帮助批改类似作业时看到的采分点分布你可以把它当作自查清单。采分点1是否在对结论分类的基础上选择正确的证明策略。能判断出 ( \Theta ) 需要双边界还是题目只要求一个方向。采分点2是否给出了显式的 c 和 n0或展示其存在性。这在 Big-O 证明中占了相当大的比重。采分点3不等式推导是否每一步都有依据。每步放缩用到的中间结论如 ( \log n \le n )是否明确写出。采分点4最终结论是否准确回扣题干函数没有把题中的 ( f(n) ) 反过来搞混。采分点5书写是否清晰变量是否一致是否出现测试性语句如“所以显然有”掩盖了推导。这一点值得多说几句。很多同学会在不等式推导中写“所以显然有”但所谓的“显然”往往正是在考场压力下最容易被忽略的、同时也是最关键的过渡。不要害怕到最后留下“c 12 和 n0 10”这种具体的数值真正的读者和老师不会觉得你笨反而会觉得你严谨。5. 实战排错我在重做习题2.2时踩过的三个坑5.1 坑一取对数比较时不小心改变了“增长层”这是我早期做排序题最容易出错的地方。取对数确实不改变增长率大小关系但容易在具体操作中算错。比如比较 ( n^{\lg n} ) 和 ( 2^n )。取对数后变成 ( \lg^2 n ) 和 ( n )。因为 ( n ) 远比 ( \lg^2 n ) 增长快所以 ( 2^n ) 快于 ( n^{\lg n} )这个结论对不对呢我们验证一下( 2^n ) 的对数是 n( n^{\lg n} ) 的对数是 ( \lg^2 n )而 ( n ) 的平方级对比 n确实是 n 占优。所以 ( 2^n ) 领先。这个例子并不难难的是在多个函数混合时你可能在取对数的过程中对某个函数少乘了一个 n导致整条排序链断裂。我的建议是取对数比较后一定要回到原函数问自己一句“这个原生形式下这个相对关系是否合理”也就是用直觉做交叉验证。如果直觉和推导矛盾多半是推导出错。5.2 坑二把 ( T(n) T(n/2) T(n/2) ) 简单等价成 ( 2T(n/2) )严格来说这两个写法在数学上是等价的但套主定理时容易给出误导。原因是如果写成 ( T(n) 2T(n/2) O(1) )那么 ( f(n) O(1) )而 ( n^{\log_2 2} n )。此时 f(n) 多项式地小于 n所以是第一种情况结果 ( \Theta(n) )。这在代数上没有错。但如果你的递归式实际上是二分法查找类的 ( T(n) T(n/2) O(1) )结果就变成 ( \Theta(\log n) )。收集这类相似题有助于你识别“相同记号下不同系数产生的实质差异”。实际上这两个递归树形态完全不同一个是二叉树的节点总数( 2n - 1 ) 量级一个是单链树的节点数( \log n ) 量级。所以看到递归式先画递归树不要急着套公式。5.3 坑三忽略常数项和低阶项的“污染”做题时经常出现这样的场景你证明了一个函数的复杂度但有一个低阶项会阻碍你的放缩。比如 ( f(n) 2n 5 )你想证明 ( f(n) O(n) )。如果取 c 2你会发现 ( 2n 5 \le 2n ) 永远不成立。于是有些人会慌乱觉得证明失败。正确的做法是意识到 Big-O 允许你选择更大的 c。取 c 7 即可因为 ( 2n 5 \le 7n ) 对所有 ( n \ge 1 ) 成立。这个“多余”的常数冗余恰恰是渐近记号宽容性的体现。遇到低阶项卡壳第一时间不是重新发明证明方法而是调大 c 或调大 n0。一个具体经验是当你的常数倍数已经很宽松仍然无法完成放缩时通常不是常数的错而是你把方向搞反了。比如你想证明 ( f \Omega(g) )却写成了 g 的常数倍小于等于 f那无论把常数调到多小都救不回来。先检查方向再调整常数。5.4 坑四附加主定理第三种情况的“正则条件”被忽略刚才提到过在第三种情况下必须检查正则条件。实际做题里有些人把主定理当作一个万能公式不检查条件就写出结论。这种“感觉上差不多”的书写方式遇到标准题可能侥幸得分但遇到变形题就是致命的。一个典型的变形( T(n) 2T(n/2) n \log n )。这里 ( \log_b a 1 )( f(n) n\log n )它比 ( n^{1} ) 大一个 ( \log n ) 因子直观看主定理第三种情况。但严格检查正则条件( 2 \cdot (n/2)\log(n/2) n\log(n/2) n\log n - n )这个值是不能被某个 ( c 1 ) 控制在 ( c \cdot n\log n ) 之下的因为相减的 n 项无法通过常数因子消除。所以第三种情况不适用。那正确结果是什么应该是 ( \Theta(n\log^2 n) )可通过递归树或代换法验证。这提醒我们不要只看“多一个对数”就跳到结论要真正检查主定理的前提。6. 复盘习题2.2训练的是读复杂度的“肌肉记忆”把习题2.2放在整本教材里看它的地位有点像一个“复杂度计算的基础设施”排序、搜索、图论算法、动态规划后面所有内容都要用到这一章建立起来的比较与推导能力。所以与其说你在做几道题不如说你在建立一套处理复杂度问题的肌肉记忆。我的建议是做完整组习题后花一点时间做一次“反推训练”——拿到一道后面的算法题哪怕是最简单的排序算法自己先写出递归式判断适合哪种解法再手动画一层递归树。这个过程不需要打开任何现成的题解纯粹靠自己的推导把复杂度走下全程。可能一开始会很慢但做上三五次之后你对习题2.2里的套路就会有内生直觉而不再需要依赖背诵。如果你正在准备考试我更建议用“一题三写”的复习方式同一道题分别用主定理、递归树、代换法各推一遍把结果交叉验证。这样做不仅加深记忆更重要的是你会发现三种方法各自的边界在哪里。这道题的哪一步用主定理最方便、哪一步画树最直观、哪一步非代换不可这些细节就是考试中真正拉分的部分。最后再分享一个实操中的小习惯我会在草稿纸上把常用的增长率排名用小字列在最上方然后把题目的函数逐个用“极限比值法”与邻近函数做比较每完成一次比较就划掉一个函数。这样排序题不仅能保证正确率还特别节省时间。这个方法在习题2.2里很基础但到了后续更难的问题中仍是最高频使用的底层层技能。