6

它来自家庭作业，但我要求一种通用方法。

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

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

但接下来呢？我在这里迷路了...

4

4 回答 4

10

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

外层将从 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))。

于 2012-08-14T08:19:40.723 回答
1

您的算法可以转换为以下形状：

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

因此，我们可以直接而正式地执行以下操作：

在此处输入图像描述

于 2014-04-05T17:38:49.673 回答
1

您以错误的方式处理此问题。要计算最坏时间，您需要找到将执行的最大操作数。因为在双循环中只有一个操作，所以找出内部循环将执行多少次就足够了。

您可以通过检查循环的限制来做到这一点。对于外循环，它是：

i^2 < N => i < sqrt(N)

您的内部循环的限制是

j < i^2

您可以在第二个等式中代入j < N.

因为这些是嵌套循环，所以您将它们的限制相乘以获得最终结果：

sqrt(N)*N = N^3/2
于 2012-08-14T08:24:26.367 回答
0

然后计算这个总和

(i^2)/2 * N^(1/2) = N/2 * N^(1/2) = N^(3/2)

于 2012-08-14T08:19:39.077 回答