有序矩阵的中位数算法

作者: , 共 753 字 , 共阅读 0

给定$ 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.

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