最坏情况下运行时间计算

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)).