Re: [问题] 给定n个排好序的整数阵列 找中位数

楼主: DJWS (...)   2014-10-17 13:56:58
FRAXIS 这是你的文章吗?
http://algnotes.wordpress.com/2014/10/09/
看完这个我就想通了
行列已排序的阵列,可以用阶梯状移动的方法找rank(做partition),O(n)
只有行排序的阵列,可以用 n 次 binary search 找 rank (做partition),O(n log n)
n个阵列长度不断改变,MoM无法保证partition出来的两堆,都是至少1/4、至多3/4,
但是MoM可以保证比MoM小的那堆至少是左上那块,至多是左上+右上+左下那三块
大 右下 右下+左下+右上
可以删掉右下(保留比MoM小的那堆)或者左上(保留比MoM大的那堆)
注意到上、下通常不一样多,但是左上右上一样多,左下右下一样多(因为中位数)
换句话说,每回合至少都会删掉“中位数较小(or大)的那些阵列的一半”
简单来说,每回合有一半的阵列至少删掉一半
所以是 O(log n) 回合没错
行列已排序是 O(n logn)
只有行排序是 O(n logn logn)
最后我还是想问,学术界有人做过这个题目吗?
还是说文章中的 reference paper 就是这个方法?
我想整理到算法笔记上面
作者: chz (稻草人骑士)   2014-10-17 14:06:00
删除的至少是"一半的行的一半",第1回是1/4,其他回不知。只知道次数一定被O(log n) bound住。
楼主: DJWS (...)   2014-10-17 14:23:00
我补了比较详细的bound方式
作者: FRAXIS (喔喔)   2014-10-17 19:35:00
Reference里面的是O(n)的方法

Links booklink

Contact Us: admin [ a t ] ucptt.com