CSP-S 提高级 · CSP 2026 提高级第一轮 第 9 题

【单选】某分治算法满足 T(n) = T(n/3) + T(2n/3) + Θ(n)，T(1) = O(1)，则 T(n) 是（ ）。

这是主定理的"非整数分割"情形：T(n) = T(n/3) + T(2n/3) + Θ(n)，两棵子树规模之和恰为 n，属于平衡划分，结果与归并排序同阶——Θ(n log n)。

看到 2n/3 就以为"分得不均所以更慢"，误选 Θ(n²) 或 θ(n^1.5)；也可能套标准主定理（要求子问题等规模）而卡住。

解析

本题考查分治算法的时间复杂度分析（递归树法）。

为什么不能直接套标准主定理

标准主定理形如 T(n) = aT(n/b) + f(n)，要求所有子问题规模相同。本题两个子问题规模分别是 n/3 和 2n/3，是不均匀划分，需要改用递归树法。

递归树逐层分析

第 0 层：1 个规模 n 的结点，本层代价 Θ(n)。

第 1 层：分成 n/3 和 2n/3 两个子问题，本层代价 = Θ(n/3) + Θ(2n/3) = Θ(n)。

第 2 层：n/3 分成 n/9、2n/9；2n/3 分成 2n/9、4n/9。本层代价 = n/9 + 2n/9 + 2n/9 + 4n/9 = Θ(n)。

一般地，每一层的结点规模之和恒为 n → 每层代价都是 Θ(n)。

关键在树的高度

递归树最深的路径是不断走 2n/3 的那一支：

n → 2n/3 → (2n/3)² → … → 1

需要满足 (2/3)^h · n = 1，即 h = log_{3/2} n = log n / log(3/2) ≈ 1.7095 · log₂n → 树高 Θ(log n)。

合并结论

T(n) = Θ(n) × Θ(log n) = Θ(n log n)

答案 A。

其他选项为什么错

• B. Θ(n²)：这是"每层代价 Θ(n) 但有 n 层"的错误假设（那是 T(n)=T(n−1)+Θ(n) 的情形）；
• C. Θ(n^1.5)：来自把指数算成 (2/3) 的某次幂；
• D. Θ(n)：只算了单层代价，忘了乘树高。

记忆点

• 不均匀划分的判定口诀：看子问题规模之和。若 Σ子规模 = n（"刚好分完"），每层代价 Θ(n)，总复杂度 = Θ(n) × 树高；
• 树高由最深的子问题决定，即由较大的那一支（2n/3）决定；
• 分治法的另一条经验：只要划分不太偏斜（每层规模之和为 n 的常数倍），复杂度就不会突破 Θ(n log n)。