Re: [理工] [資結]-交大96-複雜度

[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: 59.126.125.176
→ taitin:我是把他放大來看，當i=n的時候 j=n^2，z的每一圈都要做n^2
→ taitin:例如 i=2時，z可能每次做1，2，3，4但是我把他每次都當4看
→ taitin:當n夠大時，j跟i的迴圈碰上j%i==0 會變成 n*n+(n-1)n+n-2*n
→ taitin:              z
→ taitin:所以等於O(n^3) 加上外層i做n次 O(n^4)
→ EntHeEnd:嗯嗯... 感謝回答^^