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