Re: [問題] 給定n個排好序的整數陣列 找中位數
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間10年前 (2014/10/14 07:56)推噓5(5推 0噓 18→)留言23則, 4人參與討論串2/8 (看更多)
※ 引述《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
推
10/14 09:24, , 1F
10/14 09:24, 1F
→
10/14 09:25, , 2F
10/14 09:25, 2F
→
10/14 09:25, , 3F
10/14 09:25, 3F
→
10/14 09:26, , 4F
10/14 09:26, 4F
→
10/14 09:26, , 5F
10/14 09:26, 5F
→
10/14 09:27, , 6F
10/14 09:27, 6F
→
10/14 09:28, , 7F
10/14 09:28, 7F
→
10/14 09:28, , 8F
10/14 09:28, 8F
→
10/14 09:29, , 9F
10/14 09:29, 9F
→
10/14 11:27, , 10F
10/14 11:27, 10F
推
10/14 13:12, , 11F
10/14 13:12, 11F
→
10/14 13:13, , 12F
10/14 13:13, 12F
→
10/14 13:13, , 13F
10/14 13:13, 13F
→
10/14 15:00, , 14F
10/14 15:00, 14F
推
10/14 18:21, , 15F
10/14 18:21, 15F
→
10/14 18:21, , 16F
10/14 18:21, 16F
推
10/14 20:09, , 17F
10/14 20:09, 17F
→
10/14 20:09, , 18F
10/14 20:09, 18F
→
10/14 23:04, , 19F
10/14 23:04, 19F
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 我搞錯了 這一句當我沒說...
→
10/14 23:05, , 20F
10/14 23:05, 20F
※ 編輯: DJWS (111.250.80.176), 10/14/2014 23:51:31
推
10/15 01:27, , 21F
10/15 01:27, 21F
→
10/15 01:27, , 22F
10/15 01:27, 22F
→
10/15 01:28, , 23F
10/15 01:28, 23F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
