目标

• 解释主定理递归式中各参数的含义；
• 分析归并排序的时间、空间与比较次数；
• 判断快速排序的最好、最坏情况及稳定性；
• 识别逆序对、最大子段和和大整数乘法中的分治结构。

前置知识

建议先阅读分治模式与典型路径和正确性与复杂度分析。

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔画递归树和归并过程。
• 输入：本页按顺序给出的 10 道四选一选择题。
• 预期输出：独立作答记录，以及每道错题对应的复杂度推导或算法不变量。

作答方法

1. 复杂度题先写递归式，再比较 $f(n)$ 与 $n^{{\log }_{b}a}$；
2. 排序题明确比较次数、移动次数、辅助空间和稳定性讨论的是哪一项；
3. 点击“提交答案”后核对解析，重新推导做错的题；
4. 完成全部题目后再查看答案总览。

题型覆盖与边界

类型	本 Lab 的处理方式
归并排序	时间复杂度、辅助空间、合并比较次数与逆序对
快速排序	划分均衡性、最坏退化与稳定性
综合分治	最大子段和三类候选与 Karatsuba 子问题数
易错边界	区分渐进上界 $O$ 与紧确界 $\mathrm{\Theta }$

选择题

答题进度已答 0/10正确 0

第 1 题

难度★★考点主定理、递归式、子问题标识ch12-02-q01

在分治递归式 $T(n)=aT(n/b)+f(n)$ 中，$a$ 和 $b$ 分别表示（ ）。

查看提示

把归并排序的 $2T(n/2)+\mathrm{\Theta }(n)$ 代入理解。

请选择一个答案

A子问题个数；每个子问题相对原问题缩小的倍数

B原问题规模；子问题规模

C合并时间；分解时间

D递归深度；每层工作量

第 2 题

难度★考点归并排序、分治标识ch12-02-q02

归并排序主要采用的算法设计思想是（ ）。

查看提示

关注“分成两半后递归排序，再合并”这一过程。

请选择一个答案

A动态规划

B分治法

C贪心法

D回溯法

第 3 题

难度★考点归并排序、最坏情况、时间复杂度标识ch12-02-q03

对 $n$ 个元素进行标准归并排序，最坏情况下的渐进时间复杂度为（ ）。

查看提示

递归树每层处理多少元素？一共有多少层？

请选择一个答案

A$\mathrm{\Theta }(n)$

B$\mathrm{\Theta }(n\log n)$

C$\mathrm{\Theta }(n^2)$

D$\mathrm{\Theta }(n^2\log n)$

第 4 题

难度★★考点归并、比较次数、最坏情况标识ch12-02-q04

将两个长度均为 $n$ 的有序序列合并成一个长度为 $2n$ 的有序序列，最坏情况下需要进行多少次关键字比较？

查看提示

当某个序列耗尽后，另一个序列的剩余元素不再需要比较。

请选择一个答案

A$n$

B$n-1$

C$2n-1$

D$2n$

第 5 题

难度★★考点归并排序、空间复杂度、辅助数组标识ch12-02-q05

采用辅助数组实现标准归并排序时，其总体辅助空间复杂度为（ ）。

查看提示

辅助数组和递归栈都要考虑，最终取占用更大的数量级。

请选择一个答案

A$\mathrm{\Theta }(1)$

B$\mathrm{\Theta }(n)$

C$\mathrm{\Theta }(\log n)$

D$\mathrm{\Theta }(n^2)$

第 6 题

难度★★考点逆序对、归并排序、时间复杂度标识ch12-02-q06

在归并排序的合并过程中同步统计数组逆序对，能够达到的渐进时间复杂度是（ ）。

查看提示

不要逐对枚举；利用左右两部分已经有序这一信息批量计数。

请选择一个答案

A$\mathrm{\Theta }(n)$

B$\mathrm{\Theta }(n\log n)$

C$\mathrm{\Theta }(n^2)$

D$\mathrm{\Theta }(n^2\log n)$

第 7 题

难度★★考点快速排序、最坏情况、稳定性标识ch12-02-q07

关于采用普通二路划分的快速排序，下列说法正确的是（ ）。

查看提示

考虑每次枢轴都成为当前区间最小元素的情况。

请选择一个答案

A最坏时间复杂度为 $\mathrm{\Theta }(n\log n)$

B快速排序是稳定排序

C序列基本有序且固定取首元素为枢轴时可能退化为 $\mathrm{\Theta }(n^2)$

D每次划分都能把序列均匀分成两半

第 8 题

难度★考点快速排序、均衡划分、递归树标识ch12-02-q08

对普通二路快速排序而言，算法效率最高的典型情况是（ ）。

查看提示

比较高度为 $\log n$ 与高度为 $n$ 的递归树。

请选择一个答案

A输入完全有序且固定取首元素为枢轴

B输入完全逆序且固定取首元素为枢轴

C每次划分得到的两部分长度大致相等

D每次划分都只减少一个待处理元素

第 9 题

难度★★考点最大子段和、分治、跨中点标识ch12-02-q09

用分治法求数组最大子段和时，需要考虑的三类候选不包括（ ）。

查看提示

按一个连续区间与中点的位置关系分类。

请选择一个答案

A最大子段完全位于左半部分

B最大子段完全位于右半部分

C最大子段跨越中点

D最大子段必须覆盖整个数组

第 10 题

难度★★★考点Karatsuba、大整数乘法、主定理标识ch12-02-q10

Karatsuba 算法将一次 $n$ 位大整数乘法转化为 3 次约 $n/2$ 位乘法及线性规模的加减运算，其渐进时间复杂度约为（ ）。

查看提示

在主定理中代入 $a=3$、$b=2$。

请选择一个答案

A$\mathrm{\Theta }(n)$

B$\mathrm{\Theta }(n^{1.585})$

C$\mathrm{\Theta }(n\log n)$

D$\mathrm{\Theta }(n^2)$

答案总览（建议完成全部题目后查看）

1. 第 1 题：A
2. 第 2 题：B
3. 第 3 题：B
4. 第 4 题：C
5. 第 5 题：B
6. 第 6 题：B
7. 第 7 题：C
8. 第 8 题：C
9. 第 9 题：D
10. 第 10 题：B

完成清单

• 10 道题均在展开答案前独立作答；
• 能推导合并两个长度为 $n$ 的有序序列最多比较 $2n-1$ 次；
• 能说明快速排序退化为 $\mathrm{\Theta }(n^2)$ 的条件；
• 能写出 Karatsuba 的递归式并得到指数 ${\log }_{2}3$。

思考题

1. 为什么归并排序的初始有序程度通常不改变其渐进时间复杂度？
2. 随机选择枢轴如何降低快速排序持续出现极端划分的概率？
3. “减少一次子问题”为什么可能改变递归算法的复杂度指数？

复盘

• 我是否把辅助数组空间和递归栈空间分开分析？
• 我是否能区分快速排序的平均情况与最坏情况？
• 我能否准确指出最大子段和分治合并阶段计算的对象？