[理工] 資結 交大 複雜度
Hi,各位大大
昨日有po此題,底下的O大&信中F大
有提供我一些想法,想詢問說下面的題目
我的解法&答案是對的嗎? 我求的答案是O(n^10)
題目:
k=0;
for(i=0;i<N;i++)
for(j=0;j<i*i*i;j++)
for(z=0;z<j*j;z++)
k++;
我解題流程
n-1 i*i*i-1 j*j-1 n-1 i*i*i-1
Σ Σ Σ => Σ Σ j^2
i=0 j=0 z=0 i=0 j=0
n-1 (i*i*i-1)(i*i*i)(2i*i*i-1)
=> Σ ----------------------------
i=0 6
=> 加總內層O(i^9)，最後加總會變成O(n^10)
求得Big-O => O(n^10)
請問這一題我的答案&流程是可以的嗎? 謝謝 :)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.105.222.97
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1453122569.A.0BD.html
※ 編輯: qqoo1234 (27.105.222.97), 01/18/2016 21:10:16
推
01/18 21:35, , 1F
01/18 21:35, 1F
推
01/19 00:05, , 2F
01/19 00:05, 2F
討論串 (同標題文章)
