PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 給定n個排好序的整數陣列找中位數

看板Prob_Solve (計算數學 Problem Solving)作者chz (稻草人騎士)時間10年前 (2014/10/15 18:31)推噓8(8推 0噓 4→)

留言12則, 4人參與討論串6/8 (看更多)

※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1413369090.A.B9C.html

Re: [問題] 給定n個排好序的整數陣列 找中位數

Re: [問題] 給定n個排好序的整數陣列找中位數