有人可以告訴我爲什麼運行時間是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）。