最近开始在看DS(洪逸版书)和ALGO(林立宇笔记)有些问题想请问一下
(1)(在可用Master Theory前提下，相同题目)
我发现洪逸在讲Master Theory之前的时间复杂度(在此之前都用substitution)
答案都是写Time Complexity:O(?)
讲Master Theory之后，写的答案都是Time Complexity:θ(?)
我知道答案是O(?)的话我是可以写θ(我给了比他更好的)
但答案如果是θ(?)我不能只用O(?)表示
所以...如果我是用substitution解，我的答案就只能用O(?)吗
(除非我用substitution解完再证upper bound & Lower bound?)
(2)关于林立宇笔记的The selection problem 算法2-5框框(37页)
请问为什么第2跟第3是要分开算?
以下是我的想法
把第二步跟第三步浓缩成，第一组作sorting时找出median，第二组依序执行
直到我做到 第(n/5)堆的一半 我就知道这组的median就是median中的median p
(就是...一开始我知道有多少堆，把这堆做一半我就知道这是一半中的一半)

你并不知道第(n/5)堆的 median 就是 m-of-m's 阿

有例题吗 @@?

洪逸并没有教 substitution 吧? master前面不都展开吗

substitution就是代入展开R

喔ㄛ 了解!

substitution是拿来证明的吧？展开代入跟master thm对演算来说都只能算是“猜”答案吧 真正要证明还是只有substitution

那就是如原PO讲的那样 各自证 upper & lower bound

昨天快睡着了 QQSubstitution 有些题目依照题意 可以改成 T(n) <= ..例如像是 floor 之类的 此时 会算出 为big oh假如 依题目列出 T(n) = ... 就为 THETA这些 枫叶本 3rd 83页有类似讲解假如题目单纯给 = 就是THETA 但 假如此等式中有其他未知数 就要考虑它是在UPPER or lower bound 来决定它的等式 实际上是大于等于 还是 小于等于如同 Ky大连结内 那个T(n)式子

每堆之间没有关系啊 你没有得出每堆的中位数 怎么求得中位数的中位数（再排序堆）@@

枫叶本是 Algorithem 的圣经书 台清交都用这本