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