GESP 五级 · GESP202609 C++ 五级 第 23 题

归并排序的递推式为 $T(n) = 2T(n/2) + O(n)$，对应的时间复杂度为 $O(n \log n)$。

看到递推式先想分治法的递归结构：T(n)=2T(n/2)+O(n) 是归并排序的标准递推，合并两个有序子数组需要线性时间。展开递推：T(n)=2[2T(n/4)+n/2]+n=4T(n/4)+2n，继续展开到 T(n)=nT(1)+n log₂n，故时间复杂度为 O(n log n)。

易把归并排序与快速排序混淆，误写 T(n)=T(n-1)+O(n) 或 T(n)=2T(n/2)+O(n²)；也有考生忘记合并步骤的线性代价，只看到递归分支数就断言 O(n log n) 是巧合而非推导结果。

1. 考纲定位

本题考查 GESP 五级「算法」模块中的递推关系与分治算法，卡住的是多数考生对递归展开的机械记忆——他们背下"归并排序是 O(n log n)"，却说不清递推式为何如此、合并步骤为何是线性代价。命题人用一道判断题，把"会背"和"会推"的考生彻底分开。

2. 解题思维

归并排序是典型分治：将 n 个元素对半分成两个子问题，递归排序后合并。合并两个已排序数组需要逐个比较移动，复杂度 O(n)。因此递推式为 T(n)=2T(n/2)+O(n)。展开：

• T(n)=2T(n/2)+n
• =2[2T(n/4)+n/2]+n=4T(n/4)+2n
• =4[2T(n/8)+n/4]+2n=8T(n/8)+3n
• …
• =nT(1)+n log₂n

底数 n 时 T(1)=O(1)，故 T(n)=O(n log n)。结论：递推式正确，时间复杂度正确，选 A。