[問題] 經典的linear-time median問題
看板Prob_Solve (計算數學 Problem Solving)作者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
→
04/29 00:02, , 1F
04/29 00:02, 1F
推
04/29 00:04, , 2F
04/29 00:04, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
