[理工] [DS&ALGO]分析時間複雜度等...

看板Grad-ProbAsk作者 (-手起刀落o`)時間9年前 (2016/10/04 00:20), 9年前編輯推噓8(8推 0噓 21→)
留言29則, 5人參與, 最新討論串1/1
最近開始在看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 (就是...一開始我知道有多少堆，把這堆做一半我就知道這是一半中的一半) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.164.53.144 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1475511632.A.29A.html
推
10/04 00:26, , 1F
你並不知道第(n/5)堆的 median 就是 m-of-m's 阿
10/04 00:26, 1F
我的想法是... 假設有100個數(n=100)，分成(n/5)堆，也就是5個5個一堆總共20堆(這20堆尚未sorting) 然後開始對第一堆sorting直到第10堆的時候，我就知道這堆的median 就是median中的median
→
10/04 00:26, , 2F
有例題嗎 @@?
10/04 00:26, 2F
→
10/04 00:27, , 3F
洪逸並沒有教 substitution 吧? master前面不都展開嗎
10/04 00:27, 3F
推
10/04 00:31, , 4F
substitution就是代入展開R
10/04 00:31, 4F
→
10/04 00:36, , 5F
喔ㄛ 了解!
10/04 00:36, 5F
推
10/04 00:37, , 6F
substitution是拿來證明的吧？展開代入跟master thm
10/04 00:37, 6F
→
10/04 00:37, , 7F
對演算來說都只能算是“猜”答案吧 真正要證明還是只
10/04 00:37, 7F
→
10/04 00:37, , 8F
有substitution
10/04 00:37, 8F
據我所了解，展開帶入就是substituation，不知道為什麼這句話感覺怪怪的
→
10/04 00:37, , 9F
那就是如原PO講的那樣 各自證 upper & lower bound
10/04 00:37, 9F
※ 編輯: a19930301 (220.142.123.1), 10/04/2016 08:10:32
推
10/04 08:48, , 10F
為什麼你會覺得第十堆的median就是 m-of-m's?
10/04 08:48, 10F
→
10/04 08:48, , 11F
另外我確認了一下 substitution 是證明的方法沒錯
10/04 08:48, 11F
→
10/04 08:48, , 12F
請參考 https://goo.gl/t9xP16 代入展開並不是subst.
10/04 08:48, 12F
→
10/04 08:51, , 13F
例如有10堆的median: 8,8,8,8,3,5,4,4,4,4
10/04 08:51, 13F
→
10/04 08:54, , 14F
你說第(10/2)堆是median 這邊是3 可是並不是R 是4才對
10/04 08:54, 14F
推
10/04 08:57, , 15F
呃,,,抱歉 剛睡醒有點昏 subst.似乎就是帶入展開XD
10/04 08:57, 15F
→
10/04 08:57, , 16F
只是洪逸在教這段時 並沒有像演算法那樣很嚴謹的證明
10/04 08:57, 16F
→
10/04 08:58, , 17F
所以我有點搞混 拍謝拍謝XD
10/04 08:58, 17F
哈哈 不知道為什麼你回答的方式跟我好像XD
→
10/04 10:03, , 18F
昨天快睡著了 QQ
10/04 10:03, 18F
→
10/04 10:04, , 19F
Substitution 有些題目依照題意 可以改成 T(n) <= ..
10/04 10:04, 19F
→
10/04 10:05, , 20F
例如像是 floor 之類的 此時 會算出 為big oh
10/04 10:05, 20F
→
10/04 10:07, , 21F
假如 依題目列出 T(n) = ... 就為 THETA
10/04 10:07, 21F
→
10/04 10:08, , 22F
這些 楓葉本 3rd 83頁有類似講解
10/04 10:08, 22F
請問什麼是 楓葉本 ?
推
10/04 10:15, , 23F
假如題目單純給 = 就是THETA 但 假如此等式中有其他
10/04 10:15, 23F
→
10/04 10:15, , 24F
未知數 就要考慮它是在UPPER or lower bound 來決定
10/04 10:15, 24F
→
10/04 10:16, , 25F
它的等式 實際上是大於等於 還是 小於等於
10/04 10:16, 25F
→
10/04 10:19, , 26F
如同 Ky大連結內 那個T(n)式子
10/04 10:19, 26F
不過還是感謝解答
推
10/04 13:46, , 27F
每堆之間沒有關係啊 你沒有得出每堆的中位數 怎麼求得中
10/04 13:46, 27F
→
10/04 13:46, , 28F
位數的中位數（再排序堆）@@
10/04 13:46, 28F
我大概了解你的意思了，我還想說再排序時順便比較我要的數 但..這樣最少時間也要O(nlogn) ※ 編輯: a19930301 (36.239.191.30), 10/05/2016 23:13:55
推
10/11 15:32, , 29F
楓葉本是 Algorithem 的聖經書 台清交都用這本
10/11 15:32, 29F
‣ 更多 a19930301 的文章
文章代碼(AID): #1NyeLGAQ (Grad-ProbAsk)