作者ac01965159 (leeleo)
看板C_and_CPP
标题[问题] 请教关於时间复杂度的分析问题
时间Tue Jul 2 17:26:14 2019
这是原本的程式码
https://i.imgur.com/OL5Uicq.jpg
我尝试把他化简成以下的程式码
https://i.imgur.com/k3e0qkC.jpg
但是还是不知道该如何着手分析，拿去测试的结果大概是O(n^4)，不太了解要怎麽求出
此值，谢谢各位。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 124.9.128.132 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1562059576.A.377.html
1F：嘘 b0920075: 去看clrs 07/02 17:33
2F：→ b0920075: 按到嘘sorry 07/02 17:33
3F：→ oToToT: 化简後的那个不是可以直接算吗 07/02 18:46
4F：→ ac01965159: 抱歉因为只有修过计算机概论...还不太熟悉这类的计算 07/02 19:31
5F：→ oToToT: 那个s=\sum_{i=1}^{M}\sum_{j=1}^{i-1}i \cdot j 07/02 19:51
6F：→ oToToT: 稍微化简可以拿到这个s=(M^2(M+1)^2)/8-(M(M+1)(2M+1))/12 07/02 19:55
7F：→ oToToT: 所以是O(N^4)没错 07/02 19:55
8F：→ ac01965159: 好的，感谢。 07/02 21:29
9F：→ c910335: M是常数 O(1) 07/04 04:04