兩個代碼片段的大O符號

Question

我已經有兩段代碼和他們所屬的大O類別的解釋。然而，儘可能地嘗試一下，我無法通過觀察它或者進行樣品運行來得出解釋。

第一：

long count = 0; 
long n = 1000; 
long i, j, k; 
    for(i = 0; i < n; i++) 
     for (j = 0; j < i * i; j++) 
      for (k = 0; k < j; k++) 
       count++; 

樣品的這種運行始終給我ñ^ 4，但是我已經給出的答案是「J的特徵可以大到我^ 2，這可能是因爲大作爲N^2，k可以與j一樣大，即N^2，因此運行時間與N^N^2^N^2成正比，即爲O（N^5）「

第二代碼片段：

long i, j, k; 
long n = 1000; 
long count = 0; 
for (i = 1; i < n; i++) 
    for (j = 1; j < i * i; j++) 
     if (j % i == 0) 
      for (k = 0; k < j; k++) 
       count++; 

爲此，筆記說「if語句執行d最多N3次，但以前的論點是正確的，但只有O（N^2）次（因爲每次我都是正確的）。因此最內層的循環只執行O（N^2）次。每次通過時，需要O（j^2）= O（N^2）時間，總共O（N^4）「

爲此，筆記似乎對N^4 （雖然我一直得到N^4/10的結果），但我並沒有按照模擬計算的方式，只是對每個我都是真實的，但是，似乎進入這個循環的時間要少很多

所以問題是任何人都可以澄清什麼，我不理解

Answer 1

對於第一個：

sum from i = 0 to n-1 of 
    sum from j = 0 to i*i-1 of 
     sum from k = 0 to j-1 of 
      1 

我們知道1總和個次數爲m，所以我們可以這樣減少

sum from i = 0 to n-1 of 
    sum from j = 0 to i*i-1 of 
     j 

我們知道總和1 + 2 + ... + m = m * (m + 1)/2，所以我們可以進一步降低：

sum from i = 1 to n-1 of 
    (i * i - 1) * i * i/2 = (1/2) * (i * i * i * i - i * i) 

我們可以通過採取(1/2)外使它更簡單總結，然後拆分i * i * i * i和i * i條款;然而，總和仍然比單獨的i更難和不太知名。它確實是Theta(n^5)因此O(n^5);至少得到一個直觀的感覺，爲什麼會這樣，認識到差異f(n+1) - f(n) = (1/2)(n^4-n^2)這是在n^4的順序，所以如果f是一個連續的函數，這種差異是導數，那麼f的順序會更高。

對於第二種情況：

sum from i = 0 to n-1 of 
    sum from j = 0 to i-1 of 
     sum from k = 0 to i*j-1 
      1 

注意j現在假定只爲i最裏面的循環的目的，不同的值：0, i, 2i, ..., (i-1)i。內循環的運行次數與計數器值j的迭代次數相同。我們這樣做是爲了避免引入「階梯」符號，以便我們可以使用我們通常的數學結果。

sum from i = 0 to n-1 of 
    sum from j = 0 to i-1 of 
     i*j 

sum from i = 0 to n-1 of 
    i * (1/2) * i * (i - 1) = (1/2)(i * i * i - i) 

同樣，我們可以欺騙或做數學題，或者我們可以再次使用我們的直覺（正確）推測這原來是Theta(n^4)。