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

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

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間10年前 (2014/10/15 07:16)推噓3(3推 0噓 5→)

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

※ 引述《DJWS (...)》之銘言： : 推 springman: 其實就是用 median of median 的演算法，只是找到 10/14 09:24 : → springman: median of median m 之後，用 binary search 找出 10/14 09:25 : → springman: 每個排序的陣列中有幾個元素比 m 小，看看要找的 10/14 09:25 : → springman: median 比 m 大還是比 m 小。 10/14 09:26 : → springman: 雖然每次可能只能減少 1/4 的元素，不過沒關係。 10/14 09:26 : → springman: 每次花的時間，理論值是 O(n) 找 median of median 10/14 09:27 : → springman: O(n log n) 找比 m 小的元素個數。 10/14 09:28 : → springman: 總共應該只需要花 O(log n) 次 10/14 09:28 : → springman: 每次都要使用排序好的陣列。 10/14 09:29 : → yr: 可是 problem size 不是 n^2 嗎？這樣上面的 n 都要換成 n^2 10/14 11:27 : 推 springman: 因為 n 個 size 為 n 的數列已經排序好了 10/14 13:12 : → springman: 要算有幾個元素比 m 小時，並不是拿 n^2 個元素來比較 10/14 13:13 : → springman: 而是去每個數列做 binary search，所以時間是 O(nlogn) 10/14 13:13 : → DJWS: 第二回合要怎麼找median of median? 10/14 15:00 : 推 springman: 每一個數列是哪個範圍的元素在候選名單中需要記下來 10/14 18:21 : → springman: 候選範圍的資料的 median 同樣可以找 median。 10/14 18:21 : 推 FRAXIS: 其實找median of median可以用排序不影響複雜度 10/14 20:09 : → FRAXIS: 但是會比較容易作 10/14 20:09 : → DJWS: 應該是不得不排序為了知道「減少1/4的元素」來自哪些陣列 10/14 23:04 : 　 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 我搞錯了這一句當我沒說... : → DJWS: springman的方法看起來可行是O(n logn logn) 10/14 23:05 : ※ 編輯: DJWS (111.250.80.176), 10/14/2014 23:51:31 : 推 FRAXIS: 但是要怎麼證明一次可以刪除O(n/4)個元素？ 10/15 01:27 : → FRAXIS: 因為到最後每一列的元素都不一樣多原本median of median 10/15 01:27 : → FRAXIS: 的證明法好像不能直接套用 10/15 01:28 昨天睡覺時用力想了一陣事實上不需要跑 binary search，也不必跑 partition 這邊重新整理一下給定 n 個長度 n 已排序陣列，找第 k 小的元素每個陣列都有兩個指標 low = 0 和 high = n-1 O(n) 每個陣列的大小 size = high - low + 1 O(n) 每個陣列的中位數 array[(low + high) / 2] O(n) 上述n個中位數的中位數，設為x O(n) 套用中位數演算法注意到上述n個中位數，有一半比x小 (大) 注意到其所對應的陣列，每個陣列都有一半比x小 (大) 注意到有1/4的元素比x小 (大) 只有第一回合! 依序掃描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 大的元素得再掃描一遍n個中位數，進行實際刪除總共 O(logn) 個回合 n^2元素每回合減少1/4 的話... 總共 O(logn) 個回合每回合有一半的陣列少了一半時間複雜度 O(n logn) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.79.164 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1413328594.A.3F3.html ※ 編輯: DJWS (111.250.79.164), 10/15/2014 07:43:07

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

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