# 中位数与次序的统计

## 最大值最小值

如果同时求最大值和最小值，只需比较至多 $3\lfloor n/2\rfloor$ 次

每次挑出两个数来，先比较出它们间的大小，然后把大的和最大值比，小的和最小值比

## 第 k 大元素

可以先排序一下，然后给出第 k 个元素，时间复杂度 $O(n\lg n)$

也可以分治，每次选取一个元素，将比它小的移到前面，比它大的移到后面，然后判断第 k 大元素在哪一边，最坏时间复杂度为 $O(n^2)$，最好时间复杂度为 $O(n)$，而期望时间复杂度为 $\Theta(n)$

用 $T(n)$ 表示期望世家复杂度，令 $X_i=I\{a_q 是第 i 大的元素\}$，则有 $EX_i=\frac{1}{n}$，则有

$$T(n)\leqslant\sum_{i=1}^nX_i(T(\max(k-1,n-k))+O(n))$$

即 

$$ET(n)\leqslant\sum_{i=1}^n\frac{1}{n}ET(\max(k-1,n-k))+O(n)$$

## 最坏时间复杂度为线性的算法

思想：将数组看作一个二维数组，大小为 $m\times \lceil n/m\rceil$，对每一列求一个中间值，则中间值的中间值为作为 pivot 时可以保证有 $n/4$ 个元素比它小，$n/4$ 个元素比它大，使得之前的分治算法可以达到期望时间复杂度 $\Theta(n)$

分析：

$$T(n)=\frac{n}{m}T(m)+T(\frac{n}{m})+n+T(\frac{3n}{4})$$

其中如果 $m$ 较大，则 $\frac{n}{m}T(m)$ 已经接近 $cn$ 了，所以选取 $m=5$，而每次能至少舍掉约 $3(\frac{1}{2}\cdot\frac{n}{5})=\frac{3n}{10}$

$$T(n)=\frac{n}{5}\alpha_5+T(\frac{n}{5})+n+T(\frac{7n}{10})=\frac{n}{5}\alpha_5+T(\frac{9n}{10})+n\leqslant cn$$
有 $c\geqslant 2\alpha_5+10$