[理工] 遞迴算時間複雜度 lionlin PTT批踢踢實業坊

作者: lionlin (是正妹就K我水球) 2019-01-08 23:54:25

https://imgur.com/JE16C8A
這題想了很久不太懂
我的理解是
n>=1時每做一次分解呼叫子問題100次然後cost也是100
但是在n<1時要怎麼計算cost
n是小於1
然後i又從1 to 小於1 ?
觀念不是很清晰麻煩各位大大

作者: rockieloser (友善大隊長) 2019-01-09 00:28:00

T(n)=100*celling(T(n/10))+n*n^(1/3). T(0)=0100次的length子問題+原本要先執行的兩層迴圈不確定提供我的想法@@

作者: lionlin (是正妹就K我水球) 2019-01-09 00:35:00

大概懂你的意思 n<1時就return nil 了

作者: alen0303 (艾倫零參智商負三) 2019-01-09 00:35:00

n<1就直接return NIL了後面for迴圈就不用跑了

作者: rockieloser (友善大隊長) 2019-01-09 00:38:00

不過這樣T(0)要算1還0阿這樣算跑一行嗎發現celling括錯地方

作者: alen0303 (艾倫零參智商負三) 2019-01-09 00:44:00

代0代1應該都可以反正你列出來的都能直接master了

繼續閱讀