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

看板Prob_Solve作者mqazz1 (無法顯示)時間14年前 (2010/04/28 22:56)推噓1(1推 0噓 1→)

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

題目我想應該很多人都看過了.. 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) ------------------------------------------------------------ 還有一個也讓我不清楚的是時間複雜度的分析 T(n) ≦ cn + T(n/2) 我想請問這個式子代表什麼意思....我是有辦法解到最後是O(n) 但不太了解一開始這個式子的用意... 不好意思問題有點多謝謝!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.29.155

→

mantour

04/29 00:02, , 1^F

04/29 00:02, 1^F

推

mantour

04/29 00:04, , 2^F

04/29 00:04, 2^F

‣ 返回看板[ Prob_Solve ] 研討

‣ 更多 mqazz1 的文章

文章代碼(AID): #1Bs4oxig (Prob_Solve)