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

看板Grad-ProbAsk作者 (...)時間14年前 (2010/02/19 02:59), 編輯推噓0(0推 0噓 6→)
留言6則, 2人參與, 最新討論串3/5 (看更多)
※ 引述《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
→
02/19 10:36, , 1F
我是把他放大來看，當i=n的時候 j=n^2，z的每一圈都要做n^2
02/19 10:36, 1F
→
02/19 10:38, , 2F
例如 i=2時，z可能每次做1，2，3，4但是我把他每次都當4看
02/19 10:38, 2F
→
02/19 10:39, , 3F
當n夠大時，j跟i的迴圈碰上j%i==0 會變成 n*n+(n-1)n+n-2*n
02/19 10:39, 3F
→
02/19 10:40, , 4F
z
02/19 10:40, 4F
→
02/19 10:43, , 5F
所以等於O(n^3) 加上外層i做n次 O(n^4)
02/19 10:43, 5F
→
02/19 11:22, , 6F
嗯嗯... 感謝回答^^
02/19 11:22, 6F
‣ 更多 EntHeEnd 的文章
文章代碼(AID): #1BVOu6hi (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 3 之 5 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 EntHeEnd 的文章
文章代碼(AID): #1BVOu6hi (Grad-ProbAsk)