作者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/m.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