Re: [理工] [資結]-交大96-複雜度
最近我也做到這一題 也是疑問重重
看了版上的文章還是不懂 請問有人能再寫一次自己的解法嗎??
另外推文說到的n*n+(n-1)n+n-2*n 為什麼是O(n^3)?
※ 引述《EntHeEnd (...)》之銘言：
: ※ 引述《taitin (小南)》之銘言：
: 前文恕刪
: : e
: : i=1~n
: : j=i*i
: : if 條件成立在j為i的倍數時，又j=i^2
: : 因此我們知道共有i次會成立
: : z迴圈每次做i^2次，共做i次
: 請問為什麼 z迴圈每次做 i^2次呢 ?
: 如果j 和z迴圈一起看的話 比較像是會執行
: i + 2i +...+i^2 = i((1+i)*i/2) = O(i^3)就是了
: 不過不知道為什麼說 z迴圈"每次"做i^2次...
: 是說每次通過if(j%i==0)一次 z就做i^2次嗎... 我還是看不出來...
: : 因此 ΣO(i^3)=O(n^4)
: : i=1~n
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.171.121.161
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 5 篇)：