1. PTT
  2. C_and_CPP

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

作者: ac01965159 (leeleo)   2019-07-02 17:26:14
這是原本的程式碼https://i.imgur.com/OL5Uicq.jpg
我嘗試把他化簡成以下的程式碼
https://i.imgur.com/k3e0qkC.jpg
但是還是不知道該如何著手分析，拿去測試的結果大概是O(n^4)，不太了解要怎麼求出
此值，謝謝各位。
作者: b0920075 (Void)   2019-07-02 17:33:00
去看clrs按到噓sorry
作者: oToToT (屁孩)   2019-07-02 18:46:00
化簡後的那個不是可以直接算嗎
作者: ac01965159 (leeleo)   2019-07-02 19:31:00
抱歉因為只有修過計算機概論...還不太熟悉這類的計算
作者: oToToT (屁孩)   2019-07-02 19:51:00
那個s=\sum_{i=1}^{M}\sum_{j=1}^{i-1}i \cdot j稍微化簡可以拿到這個s=(M^2(M+1)^2)/8-(M(M+1)(2M+1))/12所以是O(N^4)沒錯
作者: ac01965159 (leeleo)   2019-07-02 21:29:00
好的，感謝。
作者: c910335 (達人)   2019-07-04 04:04:00
M是常數 O(1)
繼續閱讀
[問題] the C++ programming language裡面的問題saladimRe: [問題] 新手Overriding問題ando5566[問題] 如何同時載入分處不同文件夾的函式庫LittleLieRe: 關於c++的輸出問題djshen[問題] 新手Overriding問題b90022790[問題] 嵌入式系統的build過程dszaq[問題] dev c++ 無法儲存檔案triumphant10關於c++的輸出問題ac01965159[問題] 關於multiple definitionjames732Re: [問題] C++17 Structured binding 型別無法理解poyenc

Links booklink

Contact Us: admin [ a t ] ucptt.com