CSP-S 2026 第一轮 第 9 题：某分治算法满足 T(n)=T(n/3)+T(2n/3)+Θ(n)

题目

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

选项

• A. $Θ(n log n)$
• B. $Θ(n^{2})$
• C. $Θ(n^{1.5})$
• D. $Θ(n)$

答案

A

题解

选 A. \(\Theta(n\log n)\)。用递归树分析最直观。

每个规模为 \(m\) 的问题会分成两个子问题，规模之和为 \[ \frac m3+\frac{2m}3=m. \] 所以，在尚未出现叶子节点的层中，所有子问题的规模之和都是 \(n\)，这一层的总处理代价就是 \(\Theta(n)\)。

注意两个分支大小不同，递归树的叶子深度也不同：

• 最短路径：每次规模变为原来的 \(1/3\)，深度约为 \(\log_3 n\)。因此前 \(\Theta(\log n)\) 层，每层都有 \(\Theta(n)\) 的代价，得到下界 \(\Omega(n\log n)\)。
• 最长路径：每次规模变为原来的 \(2/3\)，深度约为 \(\log_{3/2} n\)。整棵树只有 \(O(\log n)\) 层，每层代价至多 \(O(n)\)，得到上界 \(O(n\log n)\)。

上下界一致，因此 \[ \boxed{T(n)=\Theta(n\log n)}. \]