[理工] 複雜度計算一題

[TMDTMD2487 (ㄚ冰)]

https://i.imgur.com/jkauD5Z.jpg

還請各位幫我看看我這樣寫行不行，尤其是算下限的時候結果是 C≦2

就雖然只要存在應該就沒問題了，但這種方法很少用也不確定有沒有錯XD

考試這種題目如果要寫算式，可以忽略floor跟cell嗎，還是一定要這樣算才行

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.33.7
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1511761705.A.443.html
推 ken52011219: https://i.imgur.com/CyiMZt7.jpg 手癢
推 nat99up: 覺得可以 但改的人應該會7pupu
→ ken52011219: 我發現我最後寫錯了 是OMEGA
→ ken52011219: 然後上面 寫可分成那邊我不該直接寫BIG OH 和 OMEGA
可是你圈圈1那個大於等於不合理啊@@
→ Xunion: 為什麼不直接用master
→ ken52011219: 是指T(n/2) 應該是 T(n/2-1)嗎?
→ ken52011219: 還是指上面 =>Omega(n/2) = floor(n/2) 那邊
第二個圈圈1那邊
另外如果這是計算題不能直接用master下去吧……我覺得計算題要比較計較一點啦@@
推 djmez: 計算題你要用master之前要先證明master吧 要不然會扣分
應該說當題目取floor之類的，計算題你不能直接忽略她@@
推 ken52011219: https://i.imgur.com/nBdNVk8.jpg
→ ken52011219: 這樣呢 ?
T裡面的項不能直接拆分開吧@@
我是問問有沒有人不用我的方法
其實如果這類的只能用substitution才能嚴謹的算出答案那就算了XD
※ 編輯: TMDTMD2487 (134.208.242.59), 11/27/2017 17:09:16
推 djmez: https://atekihcan.github.io/CLRS/E04.03-03/
→ djmez: 想起來CLRS有類似題目 floor不能省略但是可以像你一樣替代
→ djmez: 掉
推 djmez: https://ita.skanev.com/04/03/03.html 用官方一點的好了
推 alan23273850: 我考台大資工106的時候看到這種題目說show或justify
→ alan23273850: 就通通畫遞迴樹搭配算式展開，預估有拿到全部分數
→ alan23273850: 臨場考試的時候實在很難考慮這麼細節的東西
謝各位資結那個解答其實說穿了就是substitutionXD
也不說很細節應該說這東西題目不多，沒什麼人要你寫計算過程
所以練習量少比較不熟，考的不多就不太執著 謝謝了XD
※ 編輯: TMDTMD2487 (134.208.0.169), 11/27/2017 20:23:41