数组中的逆序对计数

算法分析

所谓逆序对，是指数组中的两个元素 $A[i]$ 和 $A[j]$，其下标 $i<j$，但是考察元素的值，却有 $A[i]>A[j]$。
输入：一个包含 $n$ 个元素的数组 $A[\mathrm{0..}n-1]$;
输出：数组中的逆序对的数目。
从最简单的实例入手:如果数组 A 只有两个元素 A[0] 和 A[1]，我们只需比较这两个元素，即可计算出逆序数。
接下来我们考虑如何求解规模更大的实例。对于一个包含 $n$ 个元素的数组 A，我们可以很容易地依据下标将 A 分解成两个小的数组，即左一半 $A[\mathrm{0..}\lceil \frac{n}{2}\rceil -1]$(简记为 $L$)和右一半 $A[\lceil \frac{n}{2}\rceil ..n-1]$(简记为 $R$)。在将大的实例分解成子实例之后，我们可以假定子实例已经求解，即使用递归调用分别求出两个元素都在 $L$ 中的逆序对数目、 以及两个元素都在 $R$ 中的逆序对数目;因此只剩下最后一个困难:如何将子实例的 解“组合”成原始给定实例的解。
逆序对计数算法中计算一个元素在右半边，一个元素在右半边的逆序对数目：如果 $L$ 和 $R$ 都已经排好序的话，只需执行 $O(n)$ 次比较即可完成逆序对的计数。

时间复杂度

$$T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)$$

选择问题：对数组的归约

如何从数组中找出第 k 小的数
输入：一个包含 $n$ 个元素的数组 $A[\mathrm{0..}n-1]$，以及一个整数 $k，(0\le k\le n-1)$;
输出：数组 $A$ 中第 $k$ 小的元素。
采用依据元素值拆分数组的方案:

选择分组中位数的中位数作为中心元

算法分析

方法：将数组$A$分组，然后以组中位数作为$A$的近似，进而以组中位数的中位数作为中心元
可以看到，组中位数的中位数在该数前面和后面均有一定量的值大于和小于他们(可以计算，如分组数为$m$，每组有$n$个数，为了方便计算，假设$m、n$都是奇数，那么比该数小的数至少有$\lceil \frac{n}{2}\rceil \times \lceil \frac{m}{2}\rceil -1$，比组中位数的中位数大的数也有$\lceil \frac{n}{2}\rceil \times \lceil \frac{m}{2}\rceil -1$个)

时间复杂度分析

算法总共需要比较的次数不超过$24n$次
$$T()\le T(\frac{n}{5})+T(\frac{7n}{10})+O(n)=O(n)$$

依据随机样本的统计量确定中间元

算法分析

构造数组的近似，一个直观的想法是对数组进行随机采样，以随机采样来近似数组，进而利用样本的统计量来确定中心元，比如采用样本中位数作为中心元，还进行一个扩展，不是只使用样本的中位数，而是使用$\frac{1}{4}分位数和$$\frac{3}{4}$分位数，将点估计扩展成区间估计。
假设随机采样的数量为$r$，采样$r$的元素得到的样本为$S$，之后计算出$S$的分位数$u$和$v$，接着对每个元素都和$u$和$v$比较，依据比较结果分别放入集合$L,M,H$，最后将$M$排序，返回其中位数作为数组的中位数估计：

时间复杂度分析

对于一个包含$n$个元素的数组$A$，当设置$r=n^{\frac{3}{4}},\delta =n^{-\frac{1}{4}}$，算法的期望时间复杂度是$O(n)$，此时位于$u,v$区间的$S$中的元素共有$n^{-\frac{1}{4}}\times r$个，所以可以期望位于$u,v$区间的$A$中的元素共有$n^{-\frac{1}{4}}\times n=n^{\frac{3}{4}}$个，所以$||M||$不会太大也不会太小

采用随机选择的一个元素作中心元

算法分析

我们有$\frac{1}{2}$的概率选到中间区域的元素，所以连续迭代两轮，可以以很高的概率使得子问题的规模呈指数级降低

时间复杂度分析

可以看到将每两次算法执行作为一期
$$T(n)=T(\frac{3n}{4})+2n=O(n)$$