作者chz (稻草人骑士)
看板Prob_Solve
标题Re: [问题] 给定n个排好序的整数阵列 找中位数
时间Wed Oct 15 18:31:28 2014
※ 引述《dreamoon (大笨蛋小月唷!)》之铭言：
: ※ 引述《DJWS (...)》之铭言：
: : 依序扫描n个中位数 O(n)
: : 比x小(大)的中位数
: : 其所对应的阵列，预计删除小(大)的那一半
: : 也就是 low = (low + high) / 2 + 1; O(1)
: : (或者 high = (low + high) / 2 - 1;)
: : 预计更新阵列大小为 size = high - low + 1 O(1)
: : 累计欲删除的元素数量 y (小的那些) O(1)
: : 如果第k个元素小於等於 y，那麽就删除最大的那 1/4，下个回合找第 k 小的元素
: : 否则就删除最小的那 1/4，下个回合找第 k = Σsize - y 大的元素
: 对於这里我有点困惑
: 若k<=y，删除叫大的那些数是没问题的，因为那些数一定比第k个数还大
: 但是当k>y时，真的能删除较小的那一部分嘛?
: 例如说现在有7*7的矩阵
: 1, 2, 3, 4, 5, 6, 7
: 8, 9,10,11,12,13,14
: 15,16,17,18,19,20,21
: 22,23,24,25,26,27,28
: 29,30,31,32,33,34,35
: 36,37,38,39,40,41,42
: 43,44,45,46,47,48,49
: 并且我要找的数是第17小的数
: 但比较小的那部分却只有16个数
: 於是按照这个演算法我们就会把真正的第17小的数给移除了0.0(我没理解错的话...)
其实把DWJS的方法稍微改一下就可以了。
对於目前的n条序各列改中位数 O(1)
n个中位数找中位数(MoM) O(n)
对每一条序列用binary search找比MoM大和小各有多少个 O(n logn)
会有 n_l个比MoM小，n_r个比MoM大，选择目标的那一边。
更新序列的 head和 tail O(1)
看把n_l或n_r被砍掉的部份算到全部被移掉的N_L和N_R中。
重复以上动作直到MoM收敛。
这个动作至多进行 O(log n)次，分析如下：
考虑n条长度为n的序列
每次动作至少有n/2条会被移除一半
也就是说，至多只要 2 log n次，所有的序列都会只剩下一个元素。
因此在经过 O(n log n log n)的时间後,还剩下O(n)个元素要找第k大的数。
再加上最後的O(n)，时间复杂度还是 O(n log n log n)。
ps. 跑实验的结果 random input大概只需要 log n个 iteration就会收敛了。
几乎不会跑到 2 log n个iteration。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.109.23.210
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1413369090.A.B9C.html
1F：推 FRAXIS: 用这个方法 解每行每列都排序的情况 就变成O(n lg n)了 10/15 20:17
2F：推 dreamoon: 我猜若只需求O(n log n log n)的话 10/15 20:48
3F：→ dreamoon: 甚至可以直接random取一个数代替MoM就行了 10/15 20:49
4F：→ chz: random取不保证收敛速度阿。 10/16 00:57
5F：推 DJWS: 用了binary search之後 每次动作不会有n/2条被移除"一半" 10/16 08:31
6F：推 DJWS: 不过用average case来分析的话 应该就对了 10/16 08:35
7F：→ DJWS: 然後这个方法拿来解每行每列都排序 依然是O(n logn logn) 10/16 08:36
8F：推 FRAXIS: 应该是变成至少有一半的列至少移除一半 10/16 21:01
9F：→ chz: n条的一半不就是 n/2条吗? 10/17 00:09
10F：推 FRAXIS: 如果每行每列都排序 partition可以在O(n)时间做完 10/17 01:05
11F：推 DJWS: 有可能删nl或nr，nl nr大小未知，为什麽是至少移除一半？ 10/17 05:50
12F：推 DJWS: 每行每列都排序 只有第一回合是这样 10/17 05:52