[理工] DS 時間複雜度 三題

[sdfg014025xx (隨便就好)]

洪逸的題庫班作業，當時期中考所以今天才寫
有些對完答案不太懂想請教各位

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1541951416.A.3E8.html
推 skyHuan: 1用sigma取for迴圈的上下界再化簡
→ skyHuan: 2題目是“exist”，如果改成任意constant就錯
推 ponponjerry: 下面那題(b)不能用Master，要用展開代入喔！我剛剛
→ ponponjerry: 寫得很亂，如果有需要我可以重寫給你參考
推 skyHuan: 咦可以master吧  我就是用master做的(?
推 alen0303: lg3大概是1.XXX 那就只要比較O(n^0.XXX)和O(logn)
→ ponponjerry: 可以嗎？！請問你ε怎麼取什麼
→ alen0303: 多項式必定比log型大 同取log比較就好了
推 skyHuan: 取0.0000001多項式還是比log大
→ ponponjerry: 對喔 我耍笨了QQ
對齁 我也忘了 感謝各位
※ 編輯: sdfg014025xx (123.195.4.87), 11/12/2018 01:06:23
推 wilson50101: 不好意思想請問一下有答案可以給我嗎？
→ wilson50101: 我補tkb可是都沒拿到答案@@
→ skyHuan: 下一堂上課會公佈喔
→ o5739201: 馬的tkb更新超慢 今天才出現第二堂
噓 skyHuan: 大碩不EY
推 EXPCDR: 不對吧第2上面那題題意是exist每錯，是錯在要大於等於n0
→ EXPCDR: 而不是大於等於1
推 skyHuan: 答案是true吧  c找再大一點n>1也會對(?
推 EXPCDR: 對欸 話說你們解答哪裡來的 第二堂課才會給嗎
→ EXPCDR: 我以為解答也是用發的