[理工] DS 時間複雜度三題 sdfg014025xx PTT批踢踢實業坊

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

作者: sdfg014025xx (隨便就好) 2018-11-11 23:50:14

洪逸的題庫班作業，當時期中考所以今天才寫
有些對完答案不太懂想請教各位
1.
https://i.imgur.com/ncK826Z.jpg
這題不太會算
2.
https://i.imgur.com/H8XJ7MY.jpg
上面那題不是應該要是positive constant才會對嗎？
下面那題好像是Master theorey case1
但是n^log3(底數2）跟nlogn要怎麼比較呢？
感謝各位

作者: skyHuan (Huan) 2018-11-12 00:11:00

1用sigma取for迴圈的上下界再化簡2題目是“exist”，如果改成任意constant就錯

作者: ponponjerry (ponpon) 2018-11-12 00:29:00

下面那題(b)不能用Master，要用展開代入喔！我剛剛寫得很亂，如果有需要我可以重寫給你參考

作者: skyHuan (Huan) 2018-11-12 00:40:00

咦可以master吧我就是用master做的(?

作者: alen0303 (艾倫零參智商負三) 2018-11-12 00:47:00

lg3大概是1.XXX 那就只要比較O(n^0.XXX)和O(logn)

作者: ponponjerry (ponpon) 2018-11-12 00:47:00

可以嗎？！請問你ε怎麼取什麼

作者: skyHuan (Huan) 2018-11-12 00:50:00

取0.0000001多項式還是比log大

作者: ponponjerry (ponpon) 2018-11-12 01:03:00

對喔我耍笨了QQ

作者: wilson50101 (我覺得我還不錯啊) 2018-11-12 17:08:00

不好意思想請問一下有答案可以給我嗎？我補tkb可是都沒拿到答案@@

作者: skyHuan (Huan) 2018-11-12 17:44:00

下一堂上課會公佈喔

作者: o5739201 (車貸學貸付二貸) 2018-11-12 21:18:00

馬的tkb更新超慢今天才出現第二堂

作者: skyHuan (Huan) 2018-11-12 21:41:00

大碩不EY

作者: EXPCDR (EXPCDR) 2018-11-13 00:29:00

不對吧第2上面那題題意是exist每錯，是錯在要大於等於n0而不是大於等於1

作者: skyHuan (Huan) 2018-11-13 01:07:00

答案是true吧 c找再大一點n>1也會對(?

作者: EXPCDR (EXPCDR) 2018-11-13 11:16:00

對欸話說你們解答哪裡來的第二堂課才會給嗎我以為解答也是用發的

繼續閱讀

[理工] OS 處理中斷的問題AAQ8 [理工] （核對）105中興離散答案a80242002 [理工] OS - response timeDora5566 Re: [理工] 計組第一章skyHuan [理工] 計組第一章AAQ8 [理工] (log(logn))!的時間複雜度cschenptt [理工] 離散問題liu1030 [理工] 離散遞迴關係式例7QoGIVoQ Re: [理工] 計組張凡（下）P.220 RAIDWillywangkaa [理工] 計組 101交大資聯 ALUChen334

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

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