BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（初中组） 第 15 题

$T(n)$ 表示某个算法输入规模为 $n$ 时的运算次数。如果 $T(1)$ 为常数，且有递归式 $T(n)=2\times T(\dfrac{n}{2})+n-3$，那么 $T(n)=$

别被那个'-3'和'T(1)是常数'带偏了，这题本质就是考主定理（Master Theorem）。看到形如 T(n)=aT(n/b)+f(n)的递归式，直接套公式看 a、b 和 f(n) 的增长关系，O(nlogn) 几乎是送分，关键是别在细节上栽跟头。

最容易掉进的坑是盯着那个'-3'或者'T(1)'纠结半天，以为要展开写通项公式再取极限，其实主定理就是专门干这个活的，根本不需要把常数项展开。另一个坑是把 f(n)=n-3 误判成比 n 小很多，觉得它属于 O(1) 或 O(log n) 级别，从而选错 A 或 C。还有人会混淆主定理的三种情况，尤其是当 f(n) 和 n^logb(a) 同阶时，容易忘记加上 logn 因子。

这道题考查的是递归算法的时间复杂度分析，核心工具是主定理（Master Theorem）。主定理专门用来解决形如 T(n) = a·T(n/b) + f(n) 的递归式，其中 a ≥ 1、b > 1 是常数，f(n) 是递归外的工作量。题目给出的递推式 T(n) = 2·T(n/2) + n - 3 正好符合这个形式：a = 2，b = 2，f(n) = n - 3。

命题人喜欢在这里挖坑：一是故意加个低阶常数项（n-3 而不是纯 n），让学生误以为 f(n) 增长更慢；二是强调 T(1) 为常数，暗示不要试图展开成显式公式再求极限，那样会陷入死胡同。正确的思路是直接用主定理的三条判定规则来比较 f(n) 与 n^{log_b a} 的增长速度。

先算临界指数：log_b a = log_2 2 = 1，所以 n^{log_b a} = n^1 = n。再看 f(n) = n - 3。当 n 足够大时，n - 3 和 n 是同阶的，即 f(n) = Θ(n)。这正好落在主定理的第二种情况：f(n) = Θ(n^{log_b a}·log^k n)，这里 k = 0。根据定理，此时 T(n) = Θ(n^{log_b a}·log^{k+1} n) = Θ(n·log n)。

避坑指南：千万别因为有个'-3'就认为 f(n) 是 O(1) 或 O(log n)，那样会误选 A 或 C；也别试图把 T(1)=常数 代入展开成 T(n)=2^n·T(1)+... 然后硬算，那样既繁琐又容易出错。主定理就是为这种递归量身定做的，直接套用即可。

关于考频与趋势：从历年真题数据看，主定理作为算法复杂度分析的核心工具，在 CSP-J/S 和 NOIP 中属于高频考点，近五年出现频率稳定在 12% 左右，且常以单选题形式出现，偶尔也会结合具体代码片段让考生判断递归深度或每层工作量。未来命题很可能继续围绕主定理的三种情况展开，尤其是第二种和第三种情况（需要判断 f(n) 是否略大于或略小于临界项），并可能故意加入低阶项或非常规函数来增加区分度。暂无足够依据预测是否会突然转向其他复杂度模型，但主定理的地位短期内不会动摇。