作者mqazz1 (無法顯示)
站內Prob_Solve
標題[問題] 經典的linear-time median問題
時間Wed Apr 28 22:56:56 2010
題目我想應該很多人都看過了..
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
1F：→ mantour:怎麼覺得若 k>[n/2] 應該是回傳SELECT(A2,k-[n/2]) 04/29 00:02