algorithm - 最坏情况运行时间计算

Question

是作业上的，求一个通用的方法。

计算以下代码在最坏情况下的运行时间。

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

答案是 N^3/2，谁能帮我解决这个问题？

有没有通用的计算方法？

This is what I thought:

when i = 0, sum++ will be called 0 time
when i = 1, sum++ will be called 1 time
when i = 2, sum++ will be called 4 times
...
when i = i, sum++ will be called i^2 times

so the worst time will be
0 + 1 + 4 + 9 + 16 + ... + i^2

但是接下来呢？？我迷路了...

Answer 1

您想计算最内层循环将运行多少次。

外层将从 i = 0 运行到 i = sqrt(N)(因为 i*i < N)。对于外部迭代的每次迭代，内部迭代将运行 i^2 次。

因此内部运行的总次数是:

1^2 + 2^2 + 3^2 + ... + sqrt(N)^2

有一个公式:

1^2 + 2^2 + ... + k^2 = k(k+1)(2k+1) / 6 = O(k^3).

在你的例子中 k = sqrt(N)。

总复杂度为 O(sqrt(N)^3) = O(N^(3/2))。