作者sdfg014025xx (隨便就好)
看板Grad-ProbAsk
標題[理工] DS 時間複雜度 三題
時間Sun Nov 11 23:50:14 2018
洪逸的題庫班作業，當時期中考所以今天才寫
有些對完答案不太懂想請教各位
1.
https://i.imgur.com/ncK826Z.jpg
這題不太會算
2.
https://i.imgur.com/H8XJ7MY.jpg
上面那題不是應該要是positive constant才會對嗎？
下面那題好像是Master theorey case1
但是n^log3(底數2）跟nlogn要怎麼比較呢？
感謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.4.87
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1541951416.A.3E8.html
1F：推 skyHuan: 1用sigma取for迴圈的上下界再化簡11/12 00:11
2F：→ skyHuan: 2題目是“exist”，如果改成任意constant就錯11/12 00:11
3F：推 ponponjerry: 下面那題(b)不能用Master，要用展開代入喔！我剛剛11/12 00:29
4F：→ ponponjerry: 寫得很亂，如果有需要我可以重寫給你參考11/12 00:29
5F：推 skyHuan: 咦可以master吧 我就是用master做的(?11/12 00:40
6F：推 alen0303: lg3大概是1.XXX 那就只要比較O(n^0.XXX)和O(logn)11/12 00:47
7F：→ ponponjerry: 可以嗎？！請問你ε怎麼取什麼11/12 00:47
8F：→ alen0303: 多項式必定比log型大 同取log比較就好了11/12 00:47
9F：推 skyHuan: 取0.0000001多項式還是比log大11/12 00:50
10F：→ ponponjerry: 對喔 我耍笨了QQ11/12 01:03
對齁 我也忘了 感謝各位
※ 編輯: sdfg014025xx (123.195.4.87), 11/12/2018 01:06:23
11F：推 wilson50101: 不好意思想請問一下有答案可以給我嗎？ 11/12 17:08
12F：→ wilson50101: 我補tkb可是都沒拿到答案@@ 11/12 17:08
13F：→ skyHuan: 下一堂上課會公佈喔 11/12 17:44
14F：→ o5739201: 馬的tkb更新超慢 今天才出現第二堂 11/12 21:18
15F：噓 skyHuan: 大碩不EY 11/12 21:41
16F：推 EXPCDR: 不對吧第2上面那題題意是exist每錯，是錯在要大於等於n0 11/13 00:29
17F：→ EXPCDR: 而不是大於等於1 11/13 00:29
18F：推 skyHuan: 答案是true吧 c找再大一點n>1也會對(? 11/13 01:07
19F：推 EXPCDR: 對欸 話說你們解答哪裡來的 第二堂課才會給嗎 11/13 11:16
20F：→ EXPCDR: 我以為解答也是用發的 11/13 11:17