作者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