java - 这段代码片段的最坏情况分析是什么？

Question

sum = 0;
for (int i = 0; i < N; i++)
  for(int j = 0; j < i*i; j++)
    sum++;

我不完全确定我的答案；我认为内循环运行 i^2 次操作而外循环运行 N 次所以最终答案是 O(N^3)？

Answer 1

操作次数是sum = 1 + 4 + 9 + ... + N^2。这是因为当 i = 0 时，j 将自增 0 次。当i = 1时，j会自增一次。当 i = 2 时，j 将自增 4 次，依此类推。

这个总和等于 N(N + 1)(2N + 1)/6，所以算法确实是 O(N^3)。你可以prove这个公式归纳。