有序矩阵的中位数算法
Zhang Zhiqiang
给一个n*n的实数矩阵，每行每列都是递增的，求其中位数算法。
听说有O(n)的算法，想了好久没想出来。
--
zhiqiang
pongba
给一个n*n的实数矩阵，每行每列都是递增的，求其中位数算法。
听说有O(n)的算法，想了好久没想出来。
--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba
HanliInter
--
Regards
Hanli Wang
__
The best way to predict the future is to invent it
Eric
复杂度是 28 n
思路是分成 5 个一组, 找中位数.
http://en.wikipedia.org/wiki/Selection_algorithm
Linear Selection 那一段
On Jun 9, 9:16 am, HanliInter <hanliin...@gmail.com> wrote:
> 阅微堂堂主？
>
> 2008/6/9 pongba <pon...@gmail.com>:
>
>
>
>
>
Eric
能否一样根据中位数的中位数找 pivot, 然后用同样的复杂度分析得到 O(n) 我想想再回复
rmq
Zhang Zhiqiang
对于矩阵，如果只有每行是递增的，有 O(n log^3 n)的算法。方法是每行中位数找中位数，每次可以将半数行的长度减去一半。
如果每行每列都是递增的，应该能做的更快。但现在还不会。
--
zhiqiang
2008/6/9 Zhang Zhiqiang <mat...@gmail.com>:
obtuseSword
在这个页面(http://med.wanfangdata.com.cn/periodical/periodical.articles/
jsjyjyfz/jsjy99/jsjy9909/990908.htm)的导言中说:
这类问题在统计学、运筹学、网络设计等方面有着实际的应用.对于一个m×n(m≤n)的列有序矩阵.Frederickson和Johnson
给出了一个时间复杂度为O(mlog(2n/m))的串行算法.该算法近乎于最优的且至今为止可能是最好的串行算法.而对于一个m×n的有序矩阵（行列
均有序），Shen等则在EREW PRAM上提出了一个时间复杂度为O(logmlogm(log logm+log(n/m))),总操作数为
O(mlog())的并行算法.
这就说明，如果只有每行是递增的方阵，复杂度也可以达到O(n)。我看到过有人证明这个问题的下界是O(nlogn)，但其实是不严格从而是有
错误的。
另外，多数人知道Tarjan等人发明的 k-选择算法 可以在O(n)时间内找出任何n个元素的中位数，乃至k-序数。我尝试把这种算法的思
路应用到这个问题上，只能得到期望时间为O(nlogn)的算法，主要是利用这样一个性质：可以在O(n)时间内确定方阵中的某个元素排在所有元素中的
次序。
On 6月10日, 上午6时42分, "Zhang Zhiqiang" <math...@gmail.com> wrote:
> 说一下我现在知道的：
>
> 对于矩阵，如果只有每行是递增的，有 O(n log^3 n)的算法。方法是每行中位数找中位数，每次可以将半数行的长度减去一半。
>
> 如果每行每列都是递增的，应该能做的更快。但现在还不会。
>
> --
> zhiqiang
>
>
>
> > 来到大牛集中营，第一次发言，大家多多关照。
>
> > 给一个n*n的实数矩阵，每行每列都是递增的，求其中位数算法。
>
> > 听说有O(n)的算法，想了好久没想出来。
>
> > --
>
> - 显示引用的文字 -
Zhang Zhiqiang
Zhang Zhiqiang
下面是这个问题的总结，原发 http://zhiqiang.org/blog/posts/median-algorithm-of-ordered-matrix.html
给定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)。
--
zhiqiang
2008/6/9 Zhang Zhiqiang <mat...@gmail.com>:
obtuseSword
如果志强兄或其它群友看懂了（或者以后看懂了），希望在此普及一下。
另外，无疑FJ-算法是比较复杂的，所以我阐述一下我将Tarjan算法应用到该问题中所能得到的较好结果，即期望时间能达到O(nlogn) 而算法
非常简洁。
这主要利用一个重要的子算法：
给定一个n*n的有序（即各行各列元素增序）方阵A=(aij)，输入行、列有序对(i,j)，我们可以利用O(n)时间确定aij在A的
n^2个元素中的次序。
统计次序的过程如下（大家最好在纸上画图演示一下）：
对于行号和列号都小（大）于i,j的元素，显然它们都小（大）于aij。 剩下未确定的元素（即aij的左下角矩阵块和右上角矩阵块），可以这样确
定：
对于左下角矩阵块，先比较aij和a(i+1,j-1)，如果 aij <= a(i+1,j-1)，那么与a(i+1,j-1)同列的下方元
素皆大于或等于aij；如果 aij>a(i+1,j-1)，那么与a(i+1,j-1)同行的左侧元素皆小于aij。 当aij<=a(i
+1,j-1)时，下一个与aij比较的元素是a(i+1,j-1)的左侧邻接元，即a(i+1,j-2)；否则，下一个比较的是a(i+1,j-1)
的下方邻接元，即a(i+2,j-1)。 类似地将此过程继续下去，直到要与aij比较的元素处于矩阵的边界。 这样，我们就将左下角矩阵块剖分成
了小于aij和大于或等于aij的两部分，自然也就统计出了这一块中有多少元素比aij小。
对于右上角矩阵块，方法类似。
通过对两个矩阵块的剖分，我们就能统计出比aij小的元素个数，从而得到aij在A中的次序。容易看出（证明），这个剖分和统计的过程时间复杂度为
O(n)。
有了上面这个子算法，我们每次在矩阵的剩余元素中随机取一个元素作为基准，统计它的次序，就能将剩余元素进一步减少，这便是Tarjan算法的思
想。 这个基准元素可以首先沿着矩阵的对角线选取，通过O(nlogn)时间将元素数目大大减少，之后再利用随机化选取。 顺便说一下，这个算法也
可以直接推广用于求解 n*m的有序矩阵的k-selection 问题。
On 6月10日, 下午7时50分, "Zhang Zhiqiang" <math...@gmail.com> wrote:
> 这里牛人果然多，一天就把我想了好久的问题解决了 :)
>
> 下面是这个问题的总结，原发http://zhiqiang.org/blog/posts/median-algorithm-of-ordered-matrix.html
> 给定n\times n的实数矩阵，每行和每列都是递增的，求这n^2个数的中位数。
>
> 但是这个问题是有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大的数。
>
Zhang Zhiqiang
zhiqiang
论文里算法的基本思路是将矩阵依次对半划分成更小的子矩阵，然后删除不可能包含所求中位数的子矩阵。通过对每次划分后子矩阵个数的估计，发现此算法时间复杂度为O(n\log2m/n)。那个删除步骤是关键。具体还是得去看原文，有点复杂，我也解释不清楚，除非长篇大论。
2008/6/11 obtuseSword <obtus...@gmail.com>:
> 后来原始论文我也找到了，但是由于英文和算法功底都很薄弱，看不懂。
> 如果志强兄或其它群友看懂了（或者以后看懂了），希望在此普及一下。
>
> 另外，无疑FJ-算法是比较复杂的，所以我阐述一下我将Tarjan算法应用到该问题中所能得到的较好结果，即期望时间能达到O(nlogn) 而算法
> 非常简洁。
>
> 这主要利用一个重要的子算法：
> 给定一个n*n的有序（即各行各列元素增序）方阵A=(aij)，输入行、列有序对(i,j)，我们可以利用O(n)时间确定aij在A的
> n^2个元素中的次序。
>
> 统计次序的过程如下（大家最好在纸上画图演示一下）：
> 对于行号和列号都小（大）于i,j的元素，显然它们都小（大）于aij。 剩下未确定的元素（即aij的左下角矩阵块和右上角矩阵块），可以这样确
> 定：
> 对于左下角矩阵块，先比较aij和a(i+1,j-1)，如果 aij <= a(i+1,j-1)，那么与a(i+1,j-1)同列的下方元
> 素皆大于或等于aij；如果 aij>a(i+1,j-1)，那么与a(i+1,j-1)同行的左侧元素皆小于aij。 当aij<=a(i
> +1,j-1)时，下一个与aij比较的元素是a(i+1,j-1)的左侧邻接元，即a(i+1,j-2)；否则，下一个比较的是a(i+1,j-1)
> 的下方邻接元，即a(i+2,j-1)。 类似地将此过程继续下去，直到要与aij比较的元素处于矩阵的边界。 这样，我们就将左下角矩阵块剖分成
> 了小于aij和大于或等于aij的两部分，自然也就统计出了这一块中有多少元素比aij小。
> 对于右上角矩阵块，方法类似。
> 通过对两个矩阵块的剖分，我们就能统计出比aij小的元素个数，从而得到aij在A中的次序。容易看出（证明），这个剖分和统计的过程时间复杂度为
> O(n)。
>
> 有了上面这个子算法，我们每次在矩阵的剩余元素中随机取一个元素作为基准，统计它的次序，就能将剩余元素进一步减少，这便是Tarjan算法的思
> 想。 这个基准元素可以首先沿着矩阵的对角线选取，通过O(nlogn)时间将元素数目大大减少，之后再利用随机化选取。 顺便说一下，这个算法也
> 可以直接推广用于求解 n*m的有序矩阵的k-selection 问题。
最后这个Ｏ(n\log n)的算法我没看懂是为什么。你说的是期望时间，对于最坏情况也是这么多么？
NjuBee
2008/6/11 Zhang Zhiqiang <mat...@gmail.com>: