作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 給定n個排好序的整數陣列 找中位數
時間Tue Oct 14 07:56:19 2014
※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1413244582.A.286.html
※ 編輯: DJWS (111.250.64.234), 10/14/2014 08:02:10
1F：推 springman: 其實就是用 median of median 的演算法，只是找到 10/14 09:24
2F：→ springman: median of median m 之後，用 binary search 找出 10/14 09:25
3F：→ springman: 每個排序的陣列中有幾個元素比 m 小，看看要找的 10/14 09:25
4F：→ springman: median 比 m 大還是比 m 小。 10/14 09:26
5F：→ springman: 雖然每次可能只能減少 1/4 的元素，不過沒關係。 10/14 09:26
6F：→ springman: 每次花的時間，理論值是 O(n) 找 median of median 10/14 09:27
7F：→ springman: O(n log n) 找比 m 小的元素個數。 10/14 09:28
8F：→ springman: 總共應該只需要花 O(log n) 次 10/14 09:28
9F：→ springman: 每次都要使用排序好的陣列。 10/14 09:29
10F：→ yr: 可是 problem size 不是 n^2 嗎？這樣上面的 n 都要換成 n^2 10/14 11:27
11F：推 springman: 因為 n 個 size 為 n 的數列已經排序好了 10/14 13:12
12F：→ springman: 要算有幾個元素比 m 小時，並不是拿 n^2 個元素來比較 10/14 13:13
13F：→ springman: 而是去每個數列做 binary search，所以時間是 O(nlogn) 10/14 13:13
14F：→ DJWS: 第二回合要怎麼找median of median? 10/14 15:00
15F：推 springman: 每一個數列是哪個範圍的元素在候選名單中需要記下來 10/14 18:21
16F：→ springman: 候選範圍的資料的 median 同樣可以找 median。 10/14 18:21
17F：推 FRAXIS: 其實找median of median可以用排序 不影響複雜度 10/14 20:09
18F：→ FRAXIS: 但是會比較容易作 10/14 20:09
19F：→ DJWS: 應該是不得不排序 為了知道「減少1/4的元素」來自哪些陣列 10/14 23:04
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 我搞錯了 這一句當我沒說...
20F：→ DJWS: springman的方法看起來可行 是O(n logn logn) 10/14 23:05
※ 編輯: DJWS (111.250.80.176), 10/14/2014 23:51:31
21F：推 FRAXIS: 但是要怎麼證明一次可以刪除O(n/4)個元素？ 10/15 01:27
22F：→ FRAXIS: 因為到最後每一列的元素都不一樣多 原本median of median 10/15 01:27
23F：→ FRAXIS: 的證明法好像不能直接套用 10/15 01:28