2
有序矩阵的中位数算法
source link: https://zhiqiang.org/cs/median-algorithm-of-ordered-matrix.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
有序矩阵的中位数算法
给定n×nn×n 的实数矩阵，每行和每列都是递增的，求这n2n2 个数的中位数。
使用类似 Tarjan 的线性中位数的方法，每次找每列中位数，然后找中位数的中位数，之后可以删除前一半列的上半部分或者后一半列的下半部分，这样可以实现复杂性O(nlog2n)O(nlog2n) 。
但是这个问题是有O(n)O(n) 的算法的，在Top Language Google Group的Obtuse Sword 的指点下，找到了这个问题的原始论文：Generalized Selection and Ranking: Sorted Matrices。事实上这篇论文证明了更强的结论：
对于一个n×mn×m (n≤mn≤m )的矩阵，若每行和每列都是递增的，则可以在O(nlog2m/n)O(nlog2m/n) 找到第kk 大的数。
算法的基本思路是将矩阵依次对半划分成更小的子矩阵，然后删除不可能包含所求中位数的子矩阵。通过对每次划分后子矩阵个数的估计，发现此算法时间复杂度为O(nlog2m/n)O(nlog2m/n) 。
使用同样的技巧，可以证明更更强的结论(这个算法具体过程就没细看了):
一堆ni×mini×mi (ni≤mini≤mi )的矩阵，若每个矩阵的每行和每列都是递增的，则 selection problem （即找第kk 大的数）的时间复杂度为O(∑nilog2mi/ni)O(∑nilog2mi/ni) 。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK