[理工] 遞迴算時間複雜度

看板Grad-ProbAsk作者 (最後的風度)時間7年前 (2019/01/08 23:54), 編輯推噓1(1推 0噓 7→)
留言8則, 3人參與, 7年前最新討論串1/1
https://imgur.com/JE16C8A
這題想了很久 不太懂 我的理解是 n>=1時 每做一次分解 呼叫子問題100次 然後cost也是100 但是在n<1時 要怎麼計算cost n是小於1 然後i又從1 to 小於1 ? 觀念不是很清晰 麻煩各位大大 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.237.211.166 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1546962870.A.694.html
→
01/09 00:28, 7年前 , 1F
T(n)=100*celling(T(n/10))+n*n^(1/3). T(0)=0
01/09 00:28, 1F
→
01/09 00:32, 7年前 , 2F
100次的length子問題+原本要先執行的兩層迴圈
01/09 00:32, 2F
→
01/09 00:33, 7年前 , 3F
不確定 提供我的想法@@
01/09 00:33, 3F
→
01/09 00:35, 7年前 , 4F
大概懂你的意思 n<1時就return nil 了
01/09 00:35, 4F
推
01/09 00:35, 7年前 , 5F
n<1就直接return NIL了 後面for迴圈就不用跑了
01/09 00:35, 5F
→
01/09 00:38, 7年前 , 6F
不過這樣T(0)要算1還0阿 這樣算跑一行嗎
01/09 00:38, 6F
→
01/09 00:41, 7年前 , 7F
發現celling括錯地方
01/09 00:41, 7F
→
01/09 00:44, 7年前 , 8F
代0代1應該都可以 反正你列出來的都能直接master了
01/09 00:44, 8F
‣ 更多 lionlin 的文章
文章代碼(AID): #1SDCUsQK (Grad-ProbAsk)