[理工] 複雜度計算一題

作者: TMDTMD2487 (ㄚ冰)   2017-11-27 13:48:23
https://i.imgur.com/jkauD5Z.jpg
還請各位幫我看看我這樣寫行不行,尤其是算下限的時候結果是 C≦2
就雖然只要存在應該就沒問題了,但這種方法很少用也不確定有沒有錯XD
考試這種題目如果要寫算式,可以忽略floor跟cell嗎,還是一定要這樣算才行
作者: ken52011219 (呱)   2017-11-27 14:54:00
作者: nat99up (NAt)   2017-11-27 15:08:00
覺得可以 但改的人應該會7pupu
作者: ken52011219 (呱)   2017-11-27 15:10:00
我發現我最後寫錯了 是OMEGA然後上面 寫可分成那邊我不該直接寫BIG OH 和 OMEGA
作者: Xunion (Xun)   2017-11-27 16:36:00
為什麼不直接用master
作者: ken52011219 (呱)   2017-11-27 16:38:00
是指T(n/2) 應該是 T(n/2-1)嗎?還是指上面 =>Omega(n/2) = floor(n/2) 那邊
作者: djmez   2017-11-27 16:53:00
計算題你要用master之前要先證明master吧 要不然會扣分
作者: ken52011219 (呱)   2017-11-27 17:00:00
作者: djmez   2017-11-27 17:44:00
https://atekihcan.github.io/CLRS/E04.03-03/想起來CLRS有類似題目 floor不能省略但是可以像你一樣替代掉https://ita.skanev.com/04/03/03.html 用官方一點的好了
作者: alan23273850   2017-11-27 18:26:00
我考台大資工106的時候看到這種題目說show或justify就通通畫遞迴樹搭配算式展開,預估有拿到全部分數臨場考試的時候實在很難考慮這麼細節的東西

Links booklink

Contact Us: admin [ a t ] ucptt.com