第六讲 Selection

选择问题（Selection）

$A[1,\cdots,n]$中的数各不相同，求其中第$k$大的数，即求第$k'=n-k+1$小的数。

基于随机化的快速选择算法（参考快速排序）

（1）随机选择一个基准$x$；

（2）将序列划分成$A[1,\cdots,i-1],A[i+1,\cdots,n]$，$A[1,\cdots,i-1]<x,A[i]=x,A[i+1,\cdots,n]>x$；

（3）若$k’<i$，则递归$\text{Quickselect}(A[1,\cdots,i-1],k')$

（4）若$k'>i$，则递归$\text{Quickselect}(A[i+1,\cdots,n],k'-i)$

（5）若$i=k’$，返回$x$

期望时间复杂度为$O(n)$

$T(n)=\displaystyle \sum_{i=1}^k T(n-i)+\sum_{i=k+1}^n T(i-1)+O(n)$

$T(n)=\displaystyle \sum_{i=1}^{n}T(\max\{i-1, n-i\})+O(n)$ $$\displaystyle T(n) \leqslant \frac{2}{n} \sum_{i=\lfloor n/2 \rfloor}^{n-1} T(i) + O(n)$$

通过数学归纳法证明 $T(n) \leqslant cn$。假设对于所有小于 $n$ 的规模，都有 $T(i) \le c i$。其中 $c$ 是待定常数。 $$\displaystyle T(n) \le \frac{2c}{n} \sum_{i=\lfloor n/2 \rfloor}^{n-1} i + an$$ $$\displaystyle T(n) \le \frac{3cn}{4} + an + \frac{c}{2}$$ 取 $c > 4a$即可。

指示变量法证明（期中不考）

假设数组排序后是：$z_1, z_2, \dots, z_n$。 * 目标点 $z_k$：我们要找的那个“全场第 $k$ 小”的数。 * 观察点 $z_j$ 和 $z_i$：我们要看这一对数字是否发生了“比较”。（假设 $i < j$）

在随机化选择中，只有当 $z_i$ 或 $z_j$ 被选为基准值时，它们才可能与对方比较。

假设$k < j$。我们要计算 $z_j$ 这一生由于 $z_k$ 的存在，总共会和它左边多少个元素发生比较。考虑 $z_k$ 到 $z_j$ 之间的这一排数：$\{z_k, z_{k+1}, \dots, z_j\}$。算法运行过程中，这组数里总会有一个数率先被随机选为 pivot。$z_i$ 和 $z_j$ 会发生比较，当且仅当从这组数里挑出的第一个 pivot 是$z_i$ 或$z_j$ 。

如果第一个挑中 $z_i$ 或 $z_j$：它们会和当前区间所有数比一遍，包括对方。
如果第一个挑中的是中间的数（比如 $z_{k+1}$）：因为目标 $z_k$ 在左边，算法会直接带队去左边，把右边的 $z_j$ 永远留在“冷宫”里，所以 $z_i$ 和 $z_j$ 再也没机会见面（比较）了。

在集合 $\{z_k, \dots, z_j\}$ 中，元素个数是 $j-k+1$。从中挑中 $z_i$ 或 $z_j$ 作为第一个 pivot 的概率是： $$Pr(z_i, z_j \text{ 比较}) = \frac{2}{\text{区间总数}} = \frac{2}{j-k+1}$$

固定 $j$，让 $i$ 从 $k$ 遍历到 $j-1$， $z_j$ 这一生跟左边这些数的比较次数期望： $$E = \sum_{i=k}^{j-1} \frac{2}{j-k+1} = (j-k) \times \frac{2}{j-k+1} < 2$$ 每个在目标右侧的数，平均只跟它左边的数比 2 次。

现在考虑 $i$ 在 $z_k$ 左侧，$j$ 在 $z_k$ 右侧的情况，即 $i < k < j$。

考虑区间 $\{z_i, z_{i+1}, \dots, z_j\}$。同样地，必须是 $z_i$ 或 $z_j$ 率先被选为 pivot，彼此之间才会发生比较。 * 如果这组数中率先选出的 pivot 是中间的那个 $z_k$，那么 $z_i$ 会被分到左边，$z_j$ 会被分到右边，导致 $z_i$ 和 $z_j$ 彻底分家，从此不再比较。

此时区间长度是 $j-i+1$。概率还是： $$Pr(z_i, z_j \text{ 比较}) = \frac{2}{j-i+1}$$

求和： $$E[\text{总次数}] = \sum_{i=1}^{k} \sum_{j=k}^{n} \frac{2}{j-i+1}=O(n)$$

快速选择算法（确定性算法）

（1）将序列分为$n/5$组，每组$5$个元素（若元素个数不为5的倍数，补充$-\text{Inf}$）

（2）取每一组的中位数$c_1,c_2,\cdots,c_{n/5}$

（3）取这些元素的中位数，记为$x$，记此元素为基准

claim：这个 $x$ 的排名大约在整体的 $30\%$ 到 $70\%$ 之间。

这 $n/5$ 个组中，至少有一半的组（ $n/10$ 组），它们的中位数 $c_i$ 是小于等于 $x$ 的。而在每一个这样的组内部，又有 3 个元素是小于等于其组中位数 $c_i$ 的。
因此至少有 $0.3n$ 的元素保证小于等于 $x$。同理，也至少有 $0.3n$ 的元素大于等于 $x$。

算法简述

（1）选取基准函数$\text{DetPivot}(A[1,\cdots,n])$

将$A$划分为$n/5$个组：$B_1,B_2,\cdots,B_{n/5}$
找到每个组的中位数：$c_1,c_2,\cdots,c_{n/5}$
$x\gets \text{DetSelect}(C[1,\cdots,n/5],n/10)$

（2）快速查找函数$\text{DetSelect}(A[1,\cdots,n],k)$（此处$k'$为对应的第$k'$小）

$x\gets \text{DetPivot}(A[1,\cdots,n])$
将序列划分成$A[1,\cdots,i-1],A[i+1,\cdots,n]$，$A[1,\cdots,i-1]<x,A[i]=x,A[i+1,\cdots,n]>x$；
若$k’<i$，则递归$\text{DetSelect}(A[1,\cdots,i-1],k')$
若$k'>i$，则递归$\text{DetSelect}(A[i+1,\cdots,n],k'-i)$
若$i=k’$，返回$x$

时间复杂度满足$T(n) \le T(0.2n) + T(0.7n + 9) + O(n)$（此处的常数9被称为边界修正项，用于保证在数学归纳法中对所有规模都严格成立。）

数学推导：假设 $T(i) \le ci$，代入： $T(n) \le 0.2cn + 0.7cn + \text{常数} + an$ $T(n) \le 0.9cn + an$ 为了满足 $0.9cn + an \le cn$，我们需要 $an \le 0.1cn$，即 $c \ge 10a$。

对于递推式$T(n)=T(\alpha n)+T(\beta n)+O(n)$，当$\alpha +\beta <1$时，算法就是$O(n)$的。

5 是能保证线性复杂度的最小奇数，在理论性能和实际开销之间取得了最佳平衡。

寻找最大最小问题（Finding Minimum & Maximum）

可知时间复杂度为$O(n)$，此处研究常数影响。

一次只求解最小值或最大值，最少需要$n-1$次比较，这毫无疑问。

如果需要一次同时求解最小值与最大值，按照常规的方法，需要比较$2n-2$次，可以优化。

考虑分组竞争优化（$3n/2$ 算法），这种方法利用了“胜者组”和“败者组”的思想。

（1）将数组元素两两成对（共 $\lfloor n/2 \rfloor$ 对），每对内部比较 1 次。

比较次数：$\lfloor n/2 \rfloor$。
结果：产生了一组“局部较小值”和一组“局部较大值”。

（2）全局最小值一定在“局部较小值”中产生。

比较次数：$\lceil n/2 \rceil - 1$。

（3）全局最大值一定在“局部较大值”中产生。

比较次数：$\lceil n/2 \rceil - 1$。
总计：约 $\mathbf{1.5n}$ 次比较（具体为 $3\lfloor n/2 \rfloor$ 次）。

最优性证明（状态标记法）

标记系统：每个元素初始有两个标记：+（可能是最大值）和 -（可能是最小值）。总标记数为 $2n$。
终止目标：最终只能剩下一个 + 和一个 -。也就是说必须消除 $2n-2$ 个标记。
比较效率：
- 只有在两个“从未被比较过”的元素之间比较时，一次比较才能消除 2 个标记（一者不再是 Max，另一者不再是 Min）。这种情况最多发生 $\lfloor n/2 \rfloor$ 次。
- 随后的比较（其中至少一个元素已经失去过标记），一次比较最多只能消除 1 个标记。
- 设总比较次数为 $C$，则消除的标记总数满足： $$2 \cdot \lfloor n/2 \rfloor + 1 \cdot (C - \lfloor n/2 \rfloor) \ge 2n - 2$$ 解得 $C \ge 2n - 2 - \lfloor n/2 \rfloor \approx 1.5n$。

为了找到第 1 大和第 2 大元素，最少需要多少次比较？ * 锦标赛法：通过树状比赛，找到最大值需要 $n-1$ 次。在比赛路径中，直接输给最大值的元素共有 $\lceil \log_2 n \rceil$ 个。第 2 大元素一定在这些“败者”中。总比较次数为 $n + \lceil \log_2 n \rceil - 2$。

多路归并排序（Selection in Sorted Arrays）（期中不考）

在 $m$ 个已经各自有序的数组中，找到全局第 $k$ 小的元素，这些元素的总数为$n$

利用“中位数的中位数”作为基准值来快速排除不可能的搜索区间。

每个数组$A_i$的中位数可以直接通过索引得到。从这 $m$ 个中位数中，再找一次中位数，记为 $x$。
在每个数组 $A_i$ 中，利用二分查找找到有多少个元素比 $x$ 小，记为 $k_i$。全局比 $x$ 小的元素总数就是 $\sum k_i$。
如果全局排名 $k$ 落在 $\sum k_i+1$ 范围内，说明我们要找的目标值在所有数组的“左半部分”，递归$\text{Select}(A_i[\le k_i],k)$，否则，目标值在“右半部分”，递归$\text{Select}(A_i[>k_i],k-\sum k_i)$部分

时间复杂度分析：

找 $m$ 个中位数的中位数需要 $O(m)$。
在 $m$ 个数组中分别做二分查找来确定 $x$ 的排名，每次二分是 $\log(n_i)$，总计 $\displaystyle O(m \log \frac{n}{m})$。

迭代次数：$\displaystyle \log \frac{n}{m}$

所有数组长度的乘积在每轮迭代中以约 $(\displaystyle \frac{1}{2})^{m/2}$ 的比例下降。这意味着搜索空间收敛得极快。

总复杂度：$\displaystyle \mathbf{O(m \log^2 \frac{n}{m})}$