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

[lionlin (最後的風度)]

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
→ rockieloser: T(n)=100*celling(T(n/10))+n*n^(1/3). T(0)=0
→ rockieloser: 100次的length子問題+原本要先執行的兩層迴圈
→ rockieloser: 不確定 提供我的想法@@
→ lionlin: 大概懂你的意思 n<1時就return nil 了
推 alen0303: n<1就直接return NIL了 後面for迴圈就不用跑了
→ rockieloser: 不過這樣T(0)要算1還0阿 這樣算跑一行嗎
→ rockieloser: 發現celling括錯地方
→ alen0303: 代0代1應該都可以 反正你列出來的都能直接master了