有序矩阵的中位数算法

作者: , 共 704 字

给定 \( 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) 课上讲的一个问题,很有意思。
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问题太快放到网上。
2007 年,我们 讨论过一个算法问题 , perfect shuffle ,据称是个微软面试题:
利用线性代数可以给某些问题很精妙的证明, Matrix67 就给出了一个这样的例子 ,这也让我想起以前看见的另外一个例子,分享如下:
首先申明一下,赌博是不对的,下面的讨论也更多是理论性的。
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是 NP 完全的 ...