时间戳

首页 > 解决方案 > Big-O 运行时间分析（for循环）

big-o - Big-O 运行时间分析（for循环）

问题描述

sum = 0;
for (i = 0; i < m; i++)
   for (j = 0; j < i*i; j++)
      for (k = 0; k < j; k++)
         sum++;

是 (1+2+...+((m-1)^2 -1)+ (m-1)^2) = (m-1)^2 *((m-1)^2 + 1) / 2 = O(m^4) 对吗？如果没有，你能帮我找到真正的解决方案和答案吗？

标签： big-ocomplexity-theory

解决方案

在这里我们有

sum(i=0..m, sum(j=0..i^2, sum(k=0..j, 1))) =
= sum(i=0..m, sum(j=0..i^2, j)) =
= sum(i=0..m, i^2*(i^2 - 1)/2) =
= sum(i=0..m, (i^4 - i^2)/2) =
= sum(i=0..m, (i^4 - i^2))/2

这是O(m^5)根据Wolfram Alpha的。

看起来您只计算了外循环最后一次迭代的结果。

这是 Wolfram Alpha 的精确计算，再次证明了O(m^5)结果

推荐阅读