Re: [問題] 經典的linear-time median問題
※ 引述《mqazz1 (無法顯示)》之銘言：
: 題目我想應該很多人都看過了..
: Suppose that you have a "black-box" worst-case linear-time median
: sub-routine. Give a simple, linear-time algorithm that solves the selection
: problem for an arbitrary order statistic.
: -----------------------------------------------------------
: 這是演算法
: An example algorithm is as follows:
: SELECTION(A, k)
: BLACK-BOX(A)
: IF k = n/2 return A[n/2]
: DIVIDE(A) /* returns A1, A2 */
: IF k < n/2 SELECTION(A1, k)
: ELSE SELECTION(A2, n/2 - k)
: END SELECTION
: ------------------------------------------------------------
: 其中，我不太懂為什麼 k > n/2 時，要在遞迴一次去SELECTION(A2, n/2 - k)
: A2 我知道是input中的右半段， 可是我不太了解 n/2 - k 代表的意思....
: 所以我比較想了解為什麼選擇的範圍是 A2 ~ (n/2 - k)
它是指搜尋 A 陣列的第 k 個
應該是如推文所說其實要是 SELECTION(A2, k - n/2)
原因你可以仔細想想 DIVIDE 拆開之後 你要抓的東西變成子序列的第幾名
: ------------------------------------------------------------
: 還有一個也讓我不清楚的是時間複雜度的分析
: T(n) ≦ cn + T(n/2)
: 我想請問這個式子代表什麼意思....我是有辦法解到最後是O(n)
: 但不太了解一開始這個式子的用意...
: 不好意思問題有點多
: 謝謝!!
於是當 A 的大小為 n 時
BLACK-BOX 花費 O(n)
DIVIDE 也是 O(n) (可參考 quick-sort 的 divide 步驟)
然後二選一呼叫一次大小為 n/2 陣列的 SELECTION
或是當運氣很好 k 是中位數則回傳
所以總時間 T(n) <= O(n) + T(n/2)
↖ ↖
前兩步 遞迴
套一下大師定理
O(n^(log_b a)) = O(n^(log_2 1)) = O(n^0) = O(n^(1-1)) apply case 3
即得結果是 O(n)
--
実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」
亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」
実琴：「難道你沒有男人的尊嚴了嗎?!」
亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」
－－プリンセス・プリンセス 第二話
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：