Re: [問題] 給定n個排好序的整數陣列 找中位數
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間10年前 (2014/10/17 19:40)推噓1(1推 0噓 3→)留言4則, 2人參與討論串8/8 (看更多)
※ 引述《DJWS (...)》之銘言：
: FRAXIS 這是你的文章嗎？
: http://algnotes.wordpress.com/2014/10/09/
哈，被發現了。
: 看完這個我就想通了
: 行列已排序的陣列，可以用階梯狀移動的方法找rank（做partition），O(n)
: 只有行排序的陣列，可以用 n 次 binary search 找 rank (做partition)，O(n log n)
: 所以是 O(log n) 回合沒錯
: 行列已排序是 O(n logn)
: 只有行排序是 O(n logn logn)
其實我之前還想到一個變形，就是給定常數個排序陣列找第 k 位。
如果套用行排序的方法，會需要O(lg^2 n)。
但是我們知道兩個陣列找中位數只需要O(lg n)的時間。
不過如果用我之前說的方法，找中位數就只需要O(lg n)的時間了。
: 最後我還是想問，學術界有人做過這個題目嗎？
: 還是說文章中的 reference paper 就是這個方法？
: 我想整理到演算法筆記上面
那篇paper是講行列排序時O(n)的方法。
只有行排序的方法，我也有找到一些資料。
http://algnotes.wordpress.com/2010/05/30/finding-median-in-3-arrays/
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.148
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1413546030.A.DC3.html
→
10/17 20:16, , 1F
10/17 20:16, 1F
推
10/17 23:49, , 2F
10/17 23:49, 2F
→
10/17 23:50, , 3F
10/17 23:50, 3F
→
10/18 03:47, , 4F
10/18 03:47, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 8 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
