algorithm - 确定这个循环问题的大 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)。那是对的吗？

标签： algorithmloopsbig-o

Answer 1