1. 拿到“习题2.1”先判断它在考你哪一项第一次做“算法设计与分析”的习题2.1时我完全把它当计算题拿计算器代值比大小然后挑一个“看起来更快”的算法。作业发下来之后被老师批注了一整段你没有回答那个“为什么”。后来才算明白这类练手题的目的是逼你从“某个输入规模下的执行时间”转向“输入规模趋向无穷时的增长规律”。很多教材把第二章放在这里是有原因的。它不要求你会发明算法只要求你掌握一种判断工具当你面前有两个候选算法其中一个在数据少时表现很好另一个在大数据的理论分析上更优你能用数学语言说清楚谁在什么区间里占优。这个能力不是刷题刷出来的它就是从一道“习题2.1”里慢慢长出来的。1.1 三种最常见的出题形式我整理了一下国内课程里常见的2.1题目把它们归纳成三类。你能在网上搜到的“算法设计与分析 习题2.1”不管出自哪本教材基本都在这个范围里出题形式考察能力典型题干信号给定多个复杂度函数要求按增长阶从小到大排序渐进阶排序“按照渐近增长率从小到大排列”给出两个算法的时间函数比较优劣渐近比较与极限计算“哪个算法渐近更优”对某段伪代码统计基本操作次数分析循环结构与计数“求出最坏情况下该算法执行的次数”这三种形式看似不同底层却共用同一套分析方法先粗略估算再严格证明最后用临界规模修正结论。2.1这个编号通常都对应教材第二章第一节也就是“算法效率分析基础”或“渐近记号”那一章所以它不会考你很难的递推求解也不会考主定理真正考的就是你能不能理解“增长阶”这三个字。1.2 这些题目背后共同的“分析逻辑”很多同学觉得“我代码能跑就行为什么要做这种数学题”这是把算法设计和算法分析混淆了。设计解决的是“怎么造出来”分析解决的是“凭什么相信它”。习题2.1逼你做的正是后者。完成一道习题2.1完整逻辑链是这样的明确一个问题规模 n从伪代码或时间函数里提取基本操作计数把这个计数化简成一个随 n 变化的函数 T(n)用渐进记号把 T(n) 归类如果需要再求两个函数相等时的临界规模 n0用来指导实际选型。这个链条看起来简单但你在后面的分治法、动态规划、回溯算法里每一步都要反复使用它。所以别看它只是小节练习这里是第一次建立“分析直觉”的地方。2. 算法分析的三大判断坐标常数、增长阶、临界规模真做题之前先把三个坐标建立起来。2.1 常数不影响渐近结论但影响工程选择假设 A 算法有 T_A(n)100nB 算法有 T_B(n)n²。乍看之下n10 时 B 只要100A 要1000好像B更好但 n1000 时A 是10万B 是100万。论渐近增长A 属于 Θ(n)B 属于 Θ(n²)B 的增长阶比A高最终一定会远远落后这是分析层面的结论。那常数有没有用当然有用。如果两个算法的增长阶相同比如一个是100n一个是50n那50n明显是两倍的现实优势。工程上常说“大 O 只是故事的一半”原因就在这里。但在习题2.1里你默认出题人关心的是“渐近意义”也就是 n 足够大之后由哪个主项来决定胜负。如果题目没有特别要求不要拿一个具体 n 值去论证谁快谁慢。2.2 记住一张增长阶排序表就能定位大多数函数我当年学这部分时自己画了一张“从慢到快”的排序表后来发现这张表几乎覆盖了算法设计与分析里90%的复杂度判断从低到高的常见增长阶Θ(1)常数时间比如取数组第一个元素Θ(log log n)极慢地增长某些并查集操作分摊后接近Θ(log n)二分查找、平衡树操作Θ(√n)试除法判素数、简单数论题Θ(n)遍历一遍所有元素Θ(n log n)快速排序、归并排序的平均/最坏Θ(n²)双层循环冒泡排序、选择排序Θ(n³)三层循环最朴素的矩阵乘法Θ(2ⁿ)枚举所有子集Θ(n!)枚举所有排列完整做到考试题时你大概率会碰到“比较 f(n)n^{3/2} 和 g(n)n log² n”这种题。它俩都介于 n 和 n² 之间单靠排序表会卡住这时候得用极限法如果 lim f(n)/g(n)0说明 f 的阶更低如果是无穷大说明 f 的阶更高如果趋近一个非零常数说明两者同阶。下面第3节我会把这个方法全部过一遍。2.3 临界规模什么时候必须把 n0 算出来第三个容易被忽略的坐标是 n0。所谓临界规模就是两个函数相等时对应的那个输入规模。n 小于 n0可能A更快大于 n0B更快。典型的例子是插入排序和归并排序插入排序最坏 Θ(n²)归并排序最坏 Θ(n log n)但插入排序的常数小在很小的数组上实际运行时间反而更短。很多标准库的排序实现会在数组长度小于一定阈值比如16或32时切换到插入排序这正是利用了 n0 的概念。练习题不会让你真的调参生产代码但很爱问“当输入规模为 200 时选哪个为 10000 时选哪个”遇到这种题你需要先建立渐近结论再求 n0然后再回答问题。只写“渐近更优”不算完整只代数值也不算完整两步结合起来才是出题人想看到的。3. 一道原型题的手算全程从函数表达式到最终结论现在进入真正的“习题2.1”环节。我以一套很接近各种教材原题的题目为例全程手算一遍。这里所有单位只是为了方便理解不影响方法本身。3.1 原型题目有两个排序算法的运行时间估计分别为T_A(n) 100n log₂n 5n微秒T_B(n) 2n² 3n微秒要求回答它们各自的增长阶是什么当 n → ∞ 时哪个渐近更优如果数据规模通常是 200应该选哪个如果是 10000 呢这道题的经典之处在于它同时考了你化简、极限、临界规模和代值判断。3.2 推导过程分五步第一步找主项。T_A 有“100n log₂n”和“5n”两项。因为 n≥2 时 log₂n ≥1所以 n log₂n 不会比 n 小随 n 增大两者差距越拉越大主项是 100n log₂n。T_B 的主项是 2n²。于是可以说T_A 的阶为 Θ(n log n)T_B 的阶为 Θ(n²)第二步用极限比较渐进阶。计算 lim_{n→∞} T_A(n) / T_B(n) lim [100n log₂n 5n] / [2n²3n] lim [100 log₂n 5] / [2n3] 0。因为 n 的增长最终压制住 log n所以 T_A/T_B 趋向于0说明 T_A 的阶比 T_B 低。n 足够大时A“渐近更优”。第三步求临界规模 n0。令 T_A(n) T_B(n)两边约掉一个 nn0100n log₂n 5n 2n² 3n 100 log₂n 5 2n 3 100 log₂n 2 2n n - 50 log₂n - 1 0。这个方程没法写出漂亮的初等解析解所以考试和工程里都用数值逼近。你可以二分n430左边≈430 - 50×8.748 -1 ≈ -8.4小于0n440左边≈440 - 50×8.781 -1 ≈ -0.05几乎等于0n445左边≈445 - 50×8.795 -1 ≈ 4.25大于0。所以临界规模约在 440 附近。注意这是一道题目的估算结果你手算时不用追求小数点后三位能判断区间就够。第四步代入题目给定的两个规模。n200 时T_A(200)100×200×log₂2005×200 ≈ 100×200×7.6441000≈153.9万微秒也就是约153.9毫秒T_B(200)2×200²3×20080600微秒约80.6毫秒。此时 B 比 A 快将近一半。虽然渐近上A更好但数据量只有200时B的多项式系数还没显示出压倒性劣势。n10000 时T_A(10000)100×10000×log₂100005×10000 ≈ 100×10000×13.28850000 ≈ 1332.8万微秒约13.3秒T_B(10000)2×10000²3×10000≈2.003亿微秒约200.3秒。差距拉到了15倍以上。这里能清楚看到随着n继续增加A的优势只会越来越大。第五步把零散结论整理成完整回答。增长阶A 为 Θ(n log n)B 为 Θ(n²)。渐近结论n→∞时A渐近更优。临界规模n0 约在 440 附近。针对性结论n200 用 Bn10000 用 A。区间结论当 1 n n0 时B占优当 n n0 时A占优。3.3 结论怎么说才完整很多人的答案里只写一句“A算法更好”这会被判不完整。我后来在批改相似习题时发现完整回答应该包含“阶渐近临界规模具体规模建议”四层。尤其当题目第3问给了具体规模就是在暗示你别忽略常数和临界规模。平时的练习可以按这个格式当作自己的答题模板考试时才不会漏信息。4. 习题2.1里最容易丢分的三个边界点在真正提交作业或上考场之前我还想列三个非常容易被扣分、但讲清楚后就能彻底避开的边界点。4.1 混淆 O、Ω、Θ 之间的语义这是一个高频失分点。O(n²) 表示上界至多是 n²Ω(n²) 表示下界至少是 n²Θ(n²) 表示“既是 O(n²) 又是 Ω(n²)”也就是精确地在这一阶上。比较方便的理解是O 像是“天花板”Ω 像是“地板”Θ 是“把地板和天花板贴到了一起”。例如说插入排序最坏情况下是 O(n²) 没错但更严格地说是 Θ(n²)因为确实存在某个输入让基本操作次数按 n² 级别增长。如果只写 O(n²) 往往会让人怀疑你是否知道它也可以被 O(n³) 盖住。习题里如果写着“给出尽可能紧的界”你用 O(n³) 当答案是会拿不到分的因为虽然从定义上说没错却不满足题的“紧致性”暗示。4.2 忽略对数的底数为什么基本可以忽略但并非完全无关很多教材会写 log n 而不写底数它的依据是换底公式log_a n log_b n / log_b a两个不同底数的对数只差一个常数因子所以在大O记号下都可以写成 Θ(log n)。这一条本身没问题但它常常被误用。误用在哪里呢有人看到“n log n 和 n log₂ n”就说“一样”这没错但当题目比较的是“n log log n”和“n log n”时就不能通过对数换底把它们化成一回事了因为这里变化的不是底数而是“内层函数”从 log n 变成了 log log n两者之间差了一个 log n 因子的量级。所以定则还是那一条底数固定时不同底数的对数可视为同阶对数里套的函数不同则不能轻易画等号。4.3 用“代入法”回答一切想看增长趋势却只看快照这是我最初犯过的错。代入法不是不能用它适合用来建立感性认识、验证数学推导不适合当作唯一的判定方法。原因很简单函数的交点未必只有一个你代入的 n 可能在交点前也可能在交点后。像上面那道题n200 时结论是“B快”n440 之后结论就翻转为“A快”。如果只代一个 n很容易得到一个“局部真理”。正确做法是先用极限或化简得到渐近阶的结论再用代入法验证几个有代表性的规模尤其是在临界规模两侧各取一个点。这样既严谨又避免纸上谈兵。5. 从习题到实战分析能力应该这么迁移说了这么多课堂上的事最后聊聊这道习题真正值钱的地方工程里的算法选型。5.1 一个真实的复杂度过高事故我之前做过一个小工具功能是合并带有相似字段的多条日志记录。最初版本用双重循环逐条比较逻辑简单五千条日志跑下来也就一两秒当时觉得“性能没问题”。后来日志量涨到五十万条程序扔进去像死了一样一个晚上都没跑完。我第一时间想到的其实是“优化常量”比如用更快的字符串比较、写缓存结果收益很有限。回头给复杂度算了一下才发现双重循环是明确的 Θ(n²)数据量翻100倍资源消耗理论上要翻一万倍小优化根本救不回来。最后把算法改成先按关键字段排序O(n log n)再线性扫描合并O(n)总复杂度落到 O(n log n)。同样数据量运行时间降到了分钟级。这个过程几乎就是习题2.1的完整复刻认清主项、判断增长阶、选择临界规模下的合理方案。5.2 我的分析流程与上机验证习惯现在每写一个可能处理大量数据的模块我都会先问自己三个问题最内层循环的基本操作是什么与 n 的关系是几次方我的算法是 Θ(n²) 还是 Θ(n log n)是否有指数级回溯风险数据规模的实际上下界是多少是否落在临界规模的同一侧问完以后写一段很小的构造数据做快速验证比如 n10³ 和 n10⁶ 各跑一次观察运行时间增长速度。这个“小样本估算-理论标注-大样本验证”的组合比任何单一手段都稳。上机实验的时候因为本质上是验证渐进阶我会把输入规模按 1、2、4、8 的比例放大看耗时是否按预期倍数增加。如果耗时涨得比预期快基本可以断定复杂度估算漏了隐藏的循环或递归。5.3 给自学者的一句话经验如果你正在自学《算法设计与分析》卡在习题2.1上我的建议是不要把时间花在背某个答案上而是把每一道题都当成一次“预测实验”先用纸笔推出为什么某种算法会赢再写一段代码验证它。当你发现纸笔结论和实测差距很大时别急着质疑理论先检查自己的复杂度表达式是不是漏了常数、缓存或递归深度。理论模型永远是对现实的高效抽象抽象出问题的时候问题大概率出在自己提取抽象的过程。那之后你会开始觉得所谓“习题2.1”其实一点不死板算法设计和算法分析本来就是一体两面设计直觉不足就找分析帮你兜底分析结论有怀疑就写代码实测。从这个角度看这道题练的早就不只是那一页作业纸了。