PTT數位生活區 / C_and_CPP (C/C++)

[問題] 請教關於時間複雜度的分析問題

看板C_and_CPP (C/C++)作者 (leeleo)時間6年前 (2019/07/02 17:26), 編輯推噓-1(0推 1噓 8→)
留言9則, 4人參與, 6年前最新討論串1/1
這是原本的程式碼https://i.imgur.com/OL5Uicq.jpg
我嘗試把他化簡成以下的程式碼 https://i.imgur.com/k3e0qkC.jpg
但是還是不知道該如何著手分析，拿去測試的結果大概是O(n^4)，不太了解要怎麼求出 此值，謝謝各位。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 124.9.128.132 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1562059576.A.377.html
噓
07/02 17:33, 6年前 , 1F
去看clrs
07/02 17:33, 1F
→
07/02 17:33, 6年前 , 2F
按到噓sorry
07/02 17:33, 2F
→
07/02 18:46, 6年前 , 3F
化簡後的那個不是可以直接算嗎
07/02 18:46, 3F
→
07/02 19:31, 6年前 , 4F
抱歉因為只有修過計算機概論...還不太熟悉這類的計算
07/02 19:31, 4F
→
07/02 19:51, 6年前 , 5F
那個s=\sum_{i=1}^{M}\sum_{j=1}^{i-1}i \cdot j
07/02 19:51, 5F
→
07/02 19:55, 6年前 , 6F
稍微化簡可以拿到這個s=(M^2(M+1)^2)/8-(M(M+1)(2M+1))/12
07/02 19:55, 6F
→
07/02 19:55, 6年前 , 7F
所以是O(N^4)沒錯
07/02 19:55, 7F
→
07/02 21:29, 6年前 , 8F
好的，感謝。
07/02 21:29, 8F
→
07/04 04:04, 6年前 , 9F
M是常數 O(1)
07/04 04:04, 9F
‣ 更多 ac01965159 的文章
文章代碼(AID): #1T6oCuDt (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 ac01965159 的文章
文章代碼(AID): #1T6oCuDt (C_and_CPP)