确定这个循环问题的大 O

Question

我不确定这个循环的大 O 成本。谁能帮我？ 我会评论我的想法。

sum = 0;  // O(1)
for(i=0;i<N;i++)
  for(j=0;j<i*i;j++)
    for(k=0;k<j;k++)  // run as 0+1²+2²+...+n²= n(n+1)(2n+1)/6
      sum++;  //  O(1)

我的猜测是 O(N^3)。对吗？

Answer 1

您的 0+1²+2²+...+n² 步估计是错误的。

最里面的循环恰好运行 0+1⁴+2⁴+...+(N-1)⁴ 次。这是前 n-1 个数字的四次方之和，即等于 n(n-1)(6(n-1)³+9(n-1)²+n-2)/30.

因此总成本为O(N⁵).

---

采用另一种方法达到相同的结果。

• 外循环刚好运行N次。
• 对于每个外部迭代，中间循环最多运行 i*i 次（即最多 N² 次）。
• 对于每个中间迭代，内部循环最多运行 j 次（即最多 N² 次）。

将成本估算相乘，总成本为 O(N⁵)。