最坏情况运行时间计算

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

但是接下来呢？我在这里迷失了方向...

- shengy

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

- Petar Ivanov

---

他的答案是一种启发式方法，在大多数情况下可能有效，但这是错误的论点 - 内部循环当然不会运行N^2次。而且你不能像它们是独立的那样简单地乘以内部和外部循环。 - Petar Ivanov

那么我可以得出结论，如果外循环和内循环是独立的，我可以简单地将它们的运行时间相乘，如 O(m*n)，但如果它们不独立，我只能手动分析并找到类似于“当 i=0 时，内循环将运行 x 次”的规律，然后将它们加在一起并找到求和公式。 - shengy

没错 - 当它们是独立的时候，你当然可以相乘。这完全取决于内部循环运行的次数 - 这才是最重要的。 - Petar Ivanov

或者我可以像kpentchev在他的答案中所做的那样，在内部循环中替换变量吗？ - shengy

明白了，计算最坏时间没有银弹可言... 最终还是得手动完成。 - shengy

Answer 2

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

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

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

- Mohamed Ennahdi El Idrissi

Answer 3

你正在错误的方式来解决这个问题。要计算最坏情况所需的时间，需要找到将执行的操作数量的最大值。因为在双重循环中只有一个操作，所以只需找出内部循环将执行多少次即可。

你可以通过检查循环的限制来完成此操作。对于外部循环，它是：

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

你的内部循环限制为

j < i^2

你可以在第二个方程中代入 j < N。

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

sqrt(N)*N = N^3/2

- kpentchev

---

通过用sqrt(N)替换i，你并没有证明复杂度为O(N^(3/2))。你只证明了复杂度<= O(N^(3/2))。因为你所做的是将其从上方限制。 - Petar Ivanov

我改正了。我的做法只适用于独立嵌套循环，而这些不是。你的公式是正确的。 - kpentchev

Answer 4

然后只需计算这个总和

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

- Herokiller