GESP 五级 · GESP 202603 C++ 五级 第 19 题

若某算法满足递推式：$T(n) = 2T(n/2) + O(n)$，则其时间复杂度为 $O(n \log n)$。

判断正误题需注意绝对化表述（"一定""必须""只能"等）往往是错误的。

判断题中注意"一定""总是""所有""唯一"等绝对化表述通常是错误的。但也要结合具体知识点判断。

【考点】递推关系式｜主定理｜时间复杂度分析

考纲定位：GESP 五级算法与程序设计模块中，递推关系式与时间复杂度是必考基础，命题人专攻考生对递归公式的"直觉判断"弱项，用经典主定理题卡住只背结论的人。

解题思维：看到 $T(n) = 2T(n/2) + O(n)$ 先识别递归树：每层规模减半，层数 $\log_2 n$，每层工作量 $n$，总复杂度 $n\log n$；主定理形式 $T(n) = aT(n/b) + f(n)$ 中 $a=2,b=2,f(n)=\Theta(n)$，对比 $n^{\log_b a}=n$，属于主定理情形二，故 $T(n)=\Theta(n\log n)$，时间复杂度为 $O(n\log n)$。

陷阱拆解：错误选项 B 往往源于误把 $O(n)$ 当成 $O(1)$ 或忽略递归层数；命题人用 $O(n)$ 而非 $\Theta(n)$ 制造"模糊边界"，诱导只记"$2T(n/2)+O(n)$"就答 $O(n)$ 的考生。绝对化表述"则其时间复杂度为 $O(n\log n)$"看似严谨，实则暗含"紧确界"要求，若只知"上界"而不知"紧确"会掉坑。

反命题思维：若把 $O(n)$ 换成 $O(n\log n)$，主定理情形变为 $f(n) = \Theta(n\log n) > n^{\log_b a}$，结果 $T(n)=\Theta(n\log^2 n)$；若改成 $T(n)=3T(n/2)+O(n)$，则 $n^{\log_b a}=n^{\log_2 3}>n$，情形一，$T(n)=\Theta(n^{\log_2 3})$。刷到类似递推题先问：$a,b$ 和 $f(n)$ 的相对阶数决定主定理情形，切勿只看系数。