有序矩阵的中位数算法

zhiqiang6月 9, 2008 计算机科学

给定 $n\times n$ 的实数矩阵，每行和每列都是递增的，求这 $n^2$ 个数的中位数。

使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数的中位数，之后可以删除前一半列的上半部分或者后一半列的下半部分，这样可以实现复杂性 $O(n\log^2n)$ 。

但是这个问题是有 $O(n)$ 的算法的，在Top Language Google Group的Obtuse Sword的指点下，找到了这个问题的原始论文：Generalized Selection and Ranking: Sorted Matrices。事实上这篇论文证明了更强的结论：

对于一个 $n\times m$ ( $n\leq m$ )的矩阵，若每行和每列都是递增的，则可以在 $O(n\log2m/n)$ 找到第 $k$ 大的数。

算法的基本思路是将矩阵依次对半划分成更小的子矩阵，然后删除不可能包含所求中位数的子矩阵。通过对每次划分后子矩阵个数的估计，发现此算法时间复杂度为 $O(n\log2m/n)$ 。

使用同样的技巧，可以证明更更强的结论(这个算法具体过程就没细看了):

一堆 $n_i\times m_i$ ( $n_i\leq m_i$ )的矩阵，若每个矩阵的每行和每列都是递增的，则selection problem（即找第 $k$ 大的数）的时间复杂度为 $O(\sum n_i\log2m_i/n_i)$ 。

你可能感兴趣的

阅微堂