[討論] 時間複雜度問題?

看板C_and_CPP作者 (CrazyDar)時間9年前 (2015/01/09 16:44), 編輯推噓3(3推 0噓 7→)
留言10則, 5人參與, 最新討論串1/1
各位大大~~ 小弟目前正陷入一個困頓之中~~ 題目如下： k=0; for(i=0;i<N;i++) for(j=0;j<i*i;j++) for(z=0;z<j;z++) k++; 請問答案是不是O(n^5) 但是解答卻是寫(n)*(n^2)*(n)=O(n^4) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.243.234.62 ※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1420793064.A.C69.html
→
01/09 16:52, , 1F
解答沒錯，你答錯。
01/09 16:52, 1F
推
01/09 17:04, , 2F
O(n^5) 沒錯: Sum(i=0,N-1,Sum(j=0,i^2-1,z=Sum(0,j-1,1)))
01/09 17:04, 2F
→
01/09 17:05, , 3F
= Sum(i=0,N-1,Sum(j=0,i^2-1,O(j)))
01/09 17:05, 3F
→
01/09 17:05, , 4F
= Sum(i=0,N-1,O(i^2)*O(i^2)) = Sum(i=0,N-1,O(i^4))
01/09 17:05, 4F
→
01/09 17:05, , 5F
= O(N^5)
01/09 17:05, 5F
→
01/09 17:06, , 6F
實際算出來會是 (2n-1)(n+1)(n)(n-1)(n-2)/20
01/09 17:06, 6F
→
01/09 17:12, , 7F
大大分解好專業~小弟用程式跑也是符合您下列的算式解
01/09 17:12, 7F
→
01/09 17:35, , 8F
OHNO
01/09 17:35, 8F
推
01/09 22:29, , 9F
好神 推
01/09 22:29, 9F
推
01/29 20:32, , 10F
推
01/29 20:32, 10F
‣ 更多 dardar923 的文章
文章代碼(AID): #1KhvJenf (C_and_CPP)