Re: [問題] 給定n個排好序的整數陣列 找中位數
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間10年前 (2014/10/17 13:57)推噓1(1推 0噓 3→)留言4則, 3人參與討論串7/8 (看更多)
FRAXIS 這是你的文章嗎？
http://algnotes.wordpress.com/2014/10/09/
看完這個我就想通了
行列已排序的陣列，可以用階梯狀移動的方法找rank（做partition），O(n)
只有行排序的陣列，可以用 n 次 binary search 找 rank (做partition)，O(n log n)
n個陣列長度不斷改變，MoM無法保證partition出來的兩堆，都是至少1/4、至多3/4，
但是MoM可以保證比MoM小的那堆至少是左上那塊，至多是左上+右上+左下那三塊
大 右下 右下+左下+右上
可以刪掉右下(保留比MoM小的那堆)或者左上(保留比MoM大的那堆)
注意到上、下通常不一樣多，但是左上右上一樣多，左下右下一樣多(因為中位數)
換句話說，每回合至少都會刪掉「中位數較小(or大)的那些陣列的一半」
簡單來說，每回合有一半的陣列至少刪掉一半
所以是 O(log n) 回合沒錯
行列已排序是 O(n logn)
只有行排序是 O(n logn logn)
最後我還是想問，學術界有人做過這個題目嗎？
還是說文章中的 reference paper 就是這個方法？
我想整理到演算法筆記上面
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.85.94
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1413525422.A.8BD.html
→
10/17 14:06, , 1F
10/17 14:06, 1F
→
10/17 14:07, , 2F
10/17 14:07, 2F
※ 編輯: DJWS (111.250.85.94), 10/17/2014 14:22:46
→
10/17 14:23, , 3F
10/17 14:23, 3F
※ 編輯: DJWS (111.250.85.94), 10/17/2014 14:27:41
※ 編輯: DJWS (111.250.85.94), 10/17/2014 14:31:32
推
10/17 19:35, , 4F
10/17 19:35, 4F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 7 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
