有序矩阵的中位数算法

511 views
Skip to first unread message

Zhang Zhiqiang

unread,
Jun 9, 2008, 12:22:26 AM6/9/08
to pon...@googlegroups.com
来到大牛集中营,第一次发言,大家多多关照。

给一个n*n的实数矩阵,每行每列都是递增的,求其中位数算法。

听说有O(n)的算法,想了好久没想出来。

--
zhiqiang

pongba

unread,
Jun 9, 2008, 1:02:55 AM6/9/08
to pon...@googlegroups.com


2008/6/9 Zhang Zhiqiang <mat...@gmail.com>:
来到大牛集中营,第一次发言,大家多多关照。

瀑布汗啊瀑布汗=.=,志强兄你自己不就是超级牛嘛:D
 
给一个n*n的实数矩阵,每行每列都是递增的,求其中位数算法。

听说有O(n)的算法,想了好久没想出来。


--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

HanliInter

unread,
Jun 9, 2008, 10:16:55 AM6/9/08
to pon...@googlegroups.com
阅微堂堂主?

2008/6/9 pongba <pon...@gmail.com>:



--
Regards
Hanli Wang
__
The best way to predict the future is to invent it

Eric

unread,
Jun 9, 2008, 10:20:53 AM6/9/08
to TopLanguage
查一下 Tarjan 的中位数算法

复杂度是 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>:
>
>
>
>
>
> > 2008/6/9 Zhang Zhiqiang <math...@gmail.com>:

Eric

unread,
Jun 9, 2008, 10:26:49 AM6/9/08
to TopLanguage
等一下 我好想搞错了, 是 n*n 找 O(n)

能否一样根据中位数的中位数找 pivot, 然后用同样的复杂度分析得到 O(n) 我想想再回复

rmq

unread,
Jun 9, 2008, 12:10:26 PM6/9/08
to TopLanguage
好难啊

Zhang Zhiqiang

unread,
Jun 9, 2008, 6:42:56 PM6/9/08
to pon...@googlegroups.com
说一下我现在知道的:

对于矩阵,如果只有每行是递增的,有 O(n log^3 n)的算法。方法是每行中位数找中位数,每次可以将半数行的长度减去一半。

如果每行每列都是递增的,应该能做的更快。但现在还不会。

--
zhiqiang


2008/6/9 Zhang Zhiqiang <mat...@gmail.com>:

obtuseSword

unread,
Jun 9, 2008, 9:11:58 PM6/9/08
to TopLanguage
这个问题好像比较困难,可以作为研究课题了。 我也先把我找到的资料列出来吧:

在这个页面(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
>
> 2008/6/9 Zhang Zhiqiang <math...@gmail.com>:
>
>
>
> > 来到大牛集中营,第一次发言,大家多多关照。
>
> > 给一个n*n的实数矩阵,每行每列都是递增的,求其中位数算法。
>
> > 听说有O(n)的算法,想了好久没想出来。
>
> > --
> > zhiqiang- 隐藏被引用文字 -
>
> - 显示引用的文字 -

Zhang Zhiqiang

unread,
Jun 9, 2008, 9:47:48 PM6/9/08
to pon...@googlegroups.com
多谢。

--
zhiqiang


2008/6/10 obtuseSword <obtus...@gmail.com>:

Zhang Zhiqiang

unread,
Jun 10, 2008, 7:50:26 AM6/10/08
to pon...@googlegroups.com
这里牛人果然多,一天就把我想了好久的问题解决了 :)

下面是这个问题的总结,原发 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

unread,
Jun 11, 2008, 4:39:18 AM6/11/08
to TopLanguage
后来原始论文我也找到了,但是由于英文和算法功底都很薄弱,看不懂。
如果志强兄或其它群友看懂了(或者以后看懂了),希望在此普及一下。

另外,无疑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个数的中位数。
>
> 使用类似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)。

Zhang Zhiqiang

unread,
Jun 11, 2008, 10:05:29 AM6/11/08
to pon...@googlegroups.com
--
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 问题。

最后这个O(n\log n)的算法我没看懂是为什么。你说的是期望时间,对于最坏情况也是这么多么?

NjuBee

unread,
Jun 12, 2008, 10:34:02 AM6/12/08
to pon...@googlegroups.com
我原来证明过有序矩阵二分查找是O(n\log2m/n), 不知是否巧合

2008/6/11 Zhang Zhiqiang <mat...@gmail.com>:

Reply all
Reply to author
Forward
0 new messages