→ taitin:用夾擊定理，然後 Σi^k =O(i^(k+1)) 02/23 21:40
→ AtonHsu:原來是這樣,謝謝:-) 02/23 21:46
這題我的疑慮是..複雜度那麼容易看出來嗎?
像遇到Σi^2的時候有公式
是用求和算子算A(X)=x^2+x/(1-x)^3算出來的
所以遇到Σi^4時,是不是也應該要用(或是事前背好)求和算子算出i^4的A(X)
然後再依據公式裡面最大的次方來判斷複雜度是多少?
上面這個想法是直覺但自己也覺得很麻煩
想請問大家面對這個問題都用什麼方法?
※ 引述《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: 120.126.97.40