为什么运行次是N^2？

Question

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

这是 Coursera 上算法课程第一部分的练习之一。

外循环是N的平方根，内循环是N(j*j)和N^3(N * N * N)的平方根。那怎么变成N^2？

Answer 1

回答这个问题有两个部分。首先，我们来讨论如何确定程序多次循环的运行ning时间。我们关心的是 sum++ 语句被调用了多少次——这就是我们要测量的。考虑这个程序：

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

首先我们看外层循环，我们看到会运行N次。现在，我们看一下内层循环，我们想知道外层循环的每次迭代运行多少次。一旦我们知道了这一点，我们就可以简单地将这两个值相乘，并获得调用 sum++ 的总次数。这样的话，很容易看出每次外层循环运行，内层循环就会运行N次。由于外层循环也是运行N次，所以这个运行ning的时间是N^2.

正如您所指出的，外循环确实是运行 sqrt(N) 次。现在，我们必须看看对于外循环的每次迭代，内循环将运行多少次。我们可以通过简化每个循环中的计数器来做到这一点。通过这样做，我们可以看到每次调用外循环时，内循环都会运行 N^(3/2)次。

为什么是这样？嗯，观察你写的相当于

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

因为对于外循环的每次迭代，我们运行内循环 N^(3/2) 次，我们可以简单地将它们相乘得到总共运行的 O( N^2).

为什么运行次是N^2？

Why the running time is N^2?

runtime