这个算法是N ^ 2吗？

Question

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

这种复杂性1 + 2^2 + 3^2 + 4^2 ... + N^2？如何用big-o表示法表示？

Answer 1

该款项是N(N+1)(2N+1)/6让你的算法O(N^3).

如果你扩大你的总和 1/3 * N^3 + ...

您可以通过绘制sum运行算法后的值来查看它的不同值N: