1.基本概念

  • 选择问题指从某集合中找出其第i个顺序统计量，即集合中第i小的元素。
  • 中位数：下中位数指第$i = \lfloor \frac{n+1}{2} \rfloor$个顺序统计量，上中位数指第$i = \lceil \frac{n+1}{2} \rceil$个顺序统计量。一般而言中位数指下中位数。
  • 最大值即第n个顺序统计量，最小值即第1个顺序统计量

2.最小值和最大值

2.1。求最大/小值算法

算法核心思想：扫描一遍数组，维护一个当前最大/小值变量即可

算法分析

该算法分析较为简单，比较次数为$n-1$，因此时间复杂度为$\Theta (n)$。

最优性

实际上算法可以看做元素之间的比赛，除了最终的胜者，其他元素必然输掉至少一场比赛(即比较一次)，因此至少做$n-1$次比较，因此也说明$MINIMUM$算法是最优的。

2.2.同时求最大、小值算法

算法核心思想：元素两两比较，小的和当前最小值比较，大的和当前最大值比较

算法分析

由于算法首先进行$\lfloor \frac{n}{2} \rfloor$次比较；
若n为奇数，将落单元素作为初始最大以及最小元，接着比较$2\frac{n-1}{2} = n-1$次
若n为偶数，接着比较$2(\frac{n}{2}-1) = n-2$次
因此该算法最少比较次数为$\lfloor \frac{3n}{2} \rfloor-2$，实际上这也是找最大以及最小值算法的最优化算法的下界

最优性

该算法的比较次数在最坏情况下是理论上最少的，下面证明同时求最大、最小值问题的最少比较次数和该算法比较次数相等，从而证明该算法的最优性
证明：
假设未进行比较比较元素为N类，进行比较后一直大于另一个元素的元素为G类，一直小于另一个元素的元素为L类，既大于其他元素又小于其他元素的记为M类
按照以上划分，可以列举出以下情况：

  • N:N产生一个G和一个L
  • N:G或者N:L产生G/L和M/G/L
  • N:M产生G/L和一个M
  • G:L产生G和L或者2M
  • G/L:M产生G/L和M或者2M

而由于最终算法结束时，需要得到G,L和(n-2)个M，因此最少的状态转换数为：$1+1+2(n-2) = 2n-2$，即从N到M必须先到G/L再到M
由于N:N能产生最多的状态转换，因此多进行N:N，最多进行$\lfloor \frac{n}{2}\rfloor$次，获得$2\lfloor \frac{n}{2}\rfloor$转换
接下来从G/L到M至少需要一次转换，要注意的是必然有一个G和一个L需要一直和无论是G/L/M进行比较（即最大值和最小值），并产生G/L和M，因此实际上每次比较只能产生一次至多一次状态转换 而对于G:L产生2M的转换，比较完后必然要将两者中原来的L和最大值比较，前者产生两次转换，后者产生0次转换，平均下来最终还是一次比较产生了一次转换。
综合上述分析总比较次数为$\lfloor \frac{n}{2}\rfloor+(2n-2-2\lfloor \frac{n}{2}\rfloor) =\lceil \frac{3n}{2}\rceil -2$，即同时找最大最小值算法的最坏情况下比较次数下界。

注意：为什么这里说最坏情况？ 最坏实际上指的是这种情况下必须要完成最少限度的比较才能确定最大最小值，其他情况例如最简单的情况：所有元素相等，显然最大值最小值都是任意元素，只需要n次比较即可。

3.随机化选择

随机化选择算法核心思想为：调用快排中$RANDOMIZED-PARTITION$算法，将数组分为大于pivot和小于pivot的两部分，并在规定的i所在数组下标范围内递归调用算法，直到pivot处于顺序统计量i位置。

随机化算法的本质在于：通过引入随机化，在$O(n)$时间内获得一个好的划分(即固定比例，例如对半)。
如果有任何其他算法可以在$O(n)$时间内获得一个好的划分，那么可以用这个算法代替$RANDOMIZED-PARTITION$算法来在$O(n)$时间内实现i-选择算法，因为最终递归方程会变为$T(n) = T(\frac{n}{k}) + O(n)$，解必然为$O(n)$

结论：随机化选择算法平均时间复杂度为$O(n)$，最坏时间复杂度为$\Theta (n^2)$

算法分析

分析时要注意，由于算法只会对i所处的子数组递归调用，假设$A[p…q]$的长度为k，因此递归方程为：
$T(n) = T(max(k-1,n-k))+O(n)$，其中$O(n)$表示随机化划分算法的运行时间上界
而由于随机化划分划分在每一个位置的概率是相等的，因此求$T(n)$的平均值（即期望）的上界如下式（上界表示有可能直接取到pivot为第i个顺序统计量，否则就递归调用）。要注意的是算法导论中给出了使用指示器变量的方法，和这里的阐述是等价的，但是推导更细致。

\[\begin{aligned} E(T(n)) & \leq \frac{1}{n}\sum_{k=1}^n T(max(k-1,n-k))+O(n) \\ & \leq \frac{2}{n}\sum_{k=\lfloor \frac{n}{2} \rfloor}^{n-1} T(k)+O(n) \end{aligned}\]

上式第二步不论对奇数n还是偶数n都成立。考虑随机划分可以认为每次都在均分，因此满足$T(n) = T(\frac{n}{2})+O(n)$，可以猜测$T(n) \leq cn$，即$T(n) = O(n)$。利用代入法有

\[\begin{aligned} E(T(n)) & \leq \frac{2}{n}\sum_{k=\lfloor \frac{n}{2} \rfloor}^{n-1} ck+O(n) \\ & = \frac{2c}{n} \frac{(\lfloor \frac{n}{2} \rfloor +n-1)(n-\lfloor \frac{n}{2} \rfloor)}{2} +O(n) \\ & = \frac{2c}{n} \frac{n^2-n+\lfloor \frac{n}{2} \rfloor(1-\lfloor \frac{n}{2} \rfloor)}{2}+O(n) \\ & \leq \frac{2c}{n} \frac{n^2-n+(\frac{n}{2}+1)(2-\frac{n}{2})}{2}+O(n) \\ & = c(\frac{3n}{4}-\frac{1}{2}+\frac{2}{n})+an \\ & = (\frac{3c}{4}+a)n+c(-\frac{1}{2}+\frac{2}{n}) \end{aligned}\]

只需$0\leq a \leq \frac{c}{4}$且$n \gt 4$，也即$n \leq 4$时$T(n) = O(1)$(此时n视为常数，因此要满足O(n)在这里即O(1))，即可满足$E(T(n)) \leq cn$对于所有$n$成立。综上，随机选择算法的平均时间复杂度为$O(n)$

4.最坏情况线性选择算法

最坏情况线性时间选择算法即$SELECT$算法，其核心思想为：保证有一个好的划分(好的划分是分组中位数的中位数)，划分并递归调用算法，直到划分元pivot处于第i顺序统计量位置即可。好的划分保证最坏时间复杂度下界为cn

算法步骤

  1. 将数组分成$\lceil \frac{n}{5} \rceil$组，每组5个元素(除了最后一组可能为$n mod 5$个)
  2. 对每一组5个元素进行插入排序，然后找到中位数
  3. 对总共$\lceil \frac{n}{5} \rceil$个中位数求中位数，求中位数的方法是递归调用本算法，将待求顺序统计量设置为中位数
  4. 以求得的中位数的中位数作为划分元，若划分元正好为第i顺序统计量那么返回，否则使用指定划分元的$PARTITION$算法进行划分
  5. 根据i顺序统计量所处位置和划分结果，递归调用本算法继续求解

算法分析

算法的核心在于获得好的划分，从而使得递归算法均衡进行。
对于1.2.4步骤，它们的时间复杂度为$O(n)$，因为1中计算$O(n)$次下标，2中是在对$O(1)$的数组进行$O(n)$次排序，4中$PARTITION$算法时间复杂度为$O(n)$
步骤3运行时间为$T(\lceil \frac{n}{5} \rceil)$
步骤5递归调用的数组大小有一个上界，这是因为中位数的中位数至少大于/小于$\lceil \frac{1}{2}\lceil \frac{n}{5} \rceil \rceil-1$个中位数，如果每一组都是5个元素，那么$\lceil \frac{1}{2}\lceil \frac{n}{5} \rceil \rceil-1$个中位数每个都大于/小于2个元素；另外考虑到有可能某中位数所在组元素少于5个，所以中位数的中位数至少大于/小于$\lceil \frac{1}{2}\lceil \frac{n}{5} \rceil \rceil-1-1$个大于/小于2个元素的中位数，也即：
中位数的中位数至少大于/小于$3(\lceil \frac{1}{2}\lceil \frac{n}{5} \rceil \rceil-2)$个元素
这也意味着步骤5递归调用的数组大小必然大于等于这个值，由于$3(\lceil \frac{1}{2}\lceil \frac{n}{5} \rceil \rceil-2) \geq \frac{3n}{10} -6$，这也意味着递归调用的数组大小必然小于等于$n-\frac{3n}{10} +6 = \frac{7n}{10}+6$
综上，对于$n\leq n_0$，T(n) = $O(1)$；对于$n\geq n_0$有：
\(\begin{aligned} T(n) & \leq O(n)+T(\lceil \frac{n}{5} \rceil)+T(\frac{7n}{10}+6) \\ \end{aligned}\)