有人可以告诉我为什么运行时间是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

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

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

首先我们看看外部循环，我们看到它会运行N次。现在，我们看看内部循环，并且我们想知道对于外部循环的每次迭代，它将运行多少次。一旦我们知道了，我们可以简单地乘以这两个值，并将获得sum ++被调用的总次数。在这种情况下，很容易看到每次外循环运行时，内循环都会运行N次。由于外循环也运行N次，所以运行时间为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）。