有序矩阵的中位数算法

作者: , 共 650 字

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

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

但是这个问题是有\( O(n)\) 的算法的,在Top Language Google GroupObtuse 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)\)

Q. E. D.

类似文章:
理论计算机(I)课上讲的一个问题,很有意思。
首先申明一下,赌博是不对的,下面的讨论也更多是理论性的。
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是NP 完全的...