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

[DJWS (...)]

※ 引述《FRAXIS (喔喔)》之銘言：
: 問題：給定 n 個已排序整數陣列，每個陣列長度為 n
:       找出 n^2 個元素中的中位數。
: 在網路上有找到幾個討論
: http://ppt.cc/PMvU
: http://ppt.cc/JE1s
:  (這是變形，給定一個n by n矩陣，每行每列都排序，找中位數)
: 但是我覺得他們的解法到最後都變成O(n^2 lg n)。
: 而如果忽略掉每個陣列都已經排序的性質，直接在 n^2 個元素中找中位數，
: 因為找中位數可以在線性時間內完成，
: 所以在 n^2 個元素內找中位數只需要O(n^2)的時間，也比網頁上的解答好。
: 有沒有比O(n^2)快的方法來解決這問題呢？
應該很難吧！

資料有 n^2 筆，然後時間複雜度是 O(n^2)，基本上已經是 linear time

要低於線性時間

要嘛略過一些資料

要嘛問題本身有很強的數學性質，可以直接推導答案

在這個問題當中，上面兩種策略似乎都行不太通


考慮 median-of-median algorithm 的第一回合

由於給定資料是 n 條已排序陣列，所以第一回合可以省下很多工夫，可以很快做完

但是找到中位數的中位數之後

接下來，還有可能是中位數的資料，約占全部的3/4

第二回合還是得處理 3/4 * n^2 這麼多資料，依舊是 O(n^2) 級別


即便我們已經知道 n 條已排序陣列，但是它的功效只能幫助我們略過 1/4 的資料

再加上中位數沒有什麼好的數學性質，尤其是可以用於精確計算的的數學性質

所以我覺得很難達成！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.64.234
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1413244582.A.286.html
※ 編輯: DJWS (111.250.64.234), 10/14/2014 08:02:10
推 springman: 其實就是用 median of median 的演算法，只是找到
→ springman: median of median m 之後，用 binary search 找出
→ springman: 每個排序的陣列中有幾個元素比 m 小，看看要找的
→ springman: median 比 m 大還是比 m 小。
→ springman: 雖然每次可能只能減少 1/4 的元素，不過沒關係。
→ springman: 每次花的時間，理論值是 O(n) 找 median of median
→ springman: O(n log n) 找比 m 小的元素個數。
→ springman: 總共應該只需要花 O(log n) 次
→ springman: 每次都要使用排序好的陣列。
→ yr: 可是 problem size 不是 n^2 嗎？這樣上面的 n 都要換成 n^2
推 springman: 因為 n 個 size 為 n 的數列已經排序好了
→ springman: 要算有幾個元素比 m 小時，並不是拿 n^2 個元素來比較
→ springman: 而是去每個數列做 binary search，所以時間是 O(nlogn)
→ DJWS: 第二回合要怎麼找median of median?
推 springman: 每一個數列是哪個範圍的元素在候選名單中需要記下來
→ springman: 候選範圍的資料的 median 同樣可以找 median。
推 FRAXIS: 其實找median of median可以用排序 不影響複雜度
→ FRAXIS: 但是會比較容易作
→ DJWS: 應該是不得不排序  為了知道「減少1/4的元素」來自哪些陣列
   　    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 我搞錯了 這一句當我沒說...
→ DJWS: springman的方法看起來可行  是O(n logn logn)
※ 編輯: DJWS (111.250.80.176), 10/14/2014 23:51:31
推 FRAXIS: 但是要怎麼證明一次可以刪除O(n/4)個元素？
→ FRAXIS: 因為到最後每一列的元素都不一樣多 原本median of median
→ FRAXIS: 的證明法好像不能直接套用