NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 14 题

假设某算法的计算时间表示为递推关系式

$T(n) = 2T(\dfrac{n}{4})+\sqrt n$

$T(1) = 1$

则算法的时间复杂度为（ ）。

这题直接套主定理，关键是算出 log₄2 等于 1/2，发现它恰好就是 √n 的指数，属于情形二，所以结果要乘一个 log n。

最容易错的是把 n^(log_4 2) 和 √n 当成不同阶，或者忽略情形二里必须多一个对数因子，直接选 B。还有人会误以为 a 和 b 是 2 和 4 就对应 O(n^2)，把底数和指数搞反。

考点概念：主定理（Master Theorem）

这道题考查的是递归式时间复杂度的求解，核心工具就是主定理。主定理专门处理形如 T(n) = a·T(n/b) + f(n) 的递推关系，通过比较 f(n) 和 n^(log_b a) 的大小来快速得出结论。

命题视角：为什么出这个数？

命题人特意选了 a=2, b=4 这种组合，就是为了制造一个“看起来像同阶，其实多一个 log”的陷阱。如果直接套用公式，很多人会忽略 log_b a 的具体数值，或者误以为只要 f(n) 是 n 的幂次就简单了。这道题的 f(n) = √n = n^(1/2)，而 log_b a = log₄2 = 1/2，两者指数完全相同，属于主定理的“情形二”，这时候答案不是简单的 n^(1/2)，而是要乘上一个 log n。