PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 經典的linear-time median問題

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 ((short)(-15074))時間14年前 (2010/04/29 01:27)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《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