最近開始在看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
(就是...一開始我知道有多少堆，把這堆做一半我就知道這是一半中的一半)
作者:
kyuudonut (善良è€ç™¾å§“)
2016-10-04 00:26:00你並不知道第(n/5)堆的 median 就是 m-of-m's 阿
作者:
kyuudonut (善良è€ç™¾å§“)
2016-10-04 00:27:00洪逸並沒有教 substitution 吧? master前面不都展開嗎
作者:
k2shouai (coding....)
2016-10-04 00:31:00substitution就是代入展開R
作者:
kyuudonut (善良è€ç™¾å§“)
2016-10-04 00:36:00喔ㄛ 了解!
substitution是拿來證明的吧？展開代入跟master thm對演算來說都只能算是“猜”答案吧 真正要證明還是只有substitution
作者:
kyuudonut (善良è€ç™¾å§“)
2016-10-04 00:37:00那就是如原PO講的那樣 各自證 upper & lower bound
昨天快睡著了 QQSubstitution 有些題目依照題意 可以改成 T(n) <= ..例如像是 floor 之類的 此時 會算出 為big oh假如 依題目列出 T(n) = ... 就為 THETA這些 楓葉本 3rd 83頁有類似講解假如題目單純給 = 就是THETA 但 假如此等式中有其他未知數 就要考慮它是在UPPER or lower bound 來決定它的等式 實際上是大於等於 還是 小於等於如同 Ky大連結內 那個T(n)式子
作者: aa06697 (todo se andarà) 2016-10-04 13:46:00
每堆之間沒有關係啊 你沒有得出每堆的中位數 怎麼求得中位數的中位數（再排序堆）@@
楓葉本是 Algorithem 的聖經書 台清交都用這本