作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 給定n個排好序的整數陣列 找中位數
時間Wed Oct 15 07:16:31 2014
※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1413328594.A.3F3.html
※ 編輯: DJWS (111.250.79.164), 10/15/2014 07:43:07
1F：推 FRAXIS: 如果每回合都有一半陣列被刪除一半 那頂多只有O(lg n)回合 10/15 07:42
2F：→ DJWS: 是這樣嗎? 要怎麼證明? 10/15 07:43
3F：→ DJWS: 好像是你說的這樣沒錯 我改一下 10/15 07:47
※ 編輯: DJWS (111.250.79.164), 10/15/2014 07:47:28
4F：→ DJWS: 然後這個方法也可以套用到已排序二維陣列 上述步驟都是O(1) 10/15 07:51
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 我又講錯了 這句話當我沒說...
5F：推 FRAXIS: 太強啦~~ 10/15 07:56
6F：→ DJWS: 感謝springman的想法 10/15 07:59
※ 編輯: DJWS (111.250.79.164), 10/15/2014 08:06:39
7F：推 springman: 您們已經想得比我多了 ^_^。 10/15 08:17
8F：→ DJWS: FRAXIS 這題目有人做過嗎？ 10/15 08:29