3個嵌套for循環的大O？

-1

public int Loop(int[] array1) { 
     int result = 0; 
     for (int i = 0; i < array1.length; i++) { 
      for (int j = 0; j < array1.length; j++) { 
       for (int k = 1; k < array1.length; k = k * 2) { 
        result += j * j * array1[k] + array1[i] + array1[j]; 
       } 
      } 
     } 
     return result; 
    }

我試圖找到計算這裏的算術運算次數的複雜度函數。我知道複雜類將是O（n^3），但我在計算步驟時遇到了一些問題。3個嵌套for循環的大O？

我的推理到目前爲止，我算的算術運算的數量是8，複雜度函數也是8n^3？

任何正確的方向指導將非常感謝，謝謝！

來源

2017-09-13 ellaaur

你確定複雜度是'O（n^3）'嗎？我的意思是，它肯定會在'O（n^3）'中，就像'O（n！）'一樣，但這不是最緊密的。 –

嗯，我的意思是我們在課堂上教過的方法是統計步數（算術運算），然後計算每次操作需要完成多少次，這就是我如何得出O（n^3）。我絕對可能是錯的。我也遵循了2個嵌套for循環的邏輯通常是我迄今爲止所做的O（n^2）。 – ellaaur

仔細考慮最內層的'ForUpdate'中的'k = k * 2'。 –

第一個循環將運行n倍，第二個循環將運行n倍然而第三循環運行log(n)次（基數2）。由於每次反操作將採取日誌時，您將乘以k兩位。乘以我們有O(n^2 log(n))

來源

2017-09-13 22:36:11 Mitchel0022

啊好的！這對複雜等級是有意義的。爲了計算確切的操作，那麼函數就是f（n）= 8n^2log（n）對不對？ – ellaaur

如果我們能同意，下面是一個很大的進步： result += j * j * array1[k] + array1[i] + array1[j] 然後讓我們稱之爲incrementResult。

incrementresult在這裏調用了多少次？ （log n）的

for (int k = 1; k < array1.length; k = k * 2) { 
    // incrementResult 
}

讓呼叫循環3。然後在這裏調用loop3多少次？ （N）

for (int j = 0; j < array1.length; j++) { 
    // loop 3 
}

我們稱之爲循環2。然後，loop2在這裏調用了多少次？ （N）

for (int i = 0; i < array1.length; i++) { 
    // loop 2 
}

乘所有這些，你會得到你的答案:)

來源

2017-09-13 22:34:25 Jon

這取決於循環。例如：

for (int i = 0; i < 10; i++) { 
    for (int j = 0; j < 10; j++) { 
     for (int k = 0; k < 10; k++) { 
      sum += i * j * k; 
     } 
    } 
}

具有複雜度O（1），因爲迭代的次數根本不依賴於輸入。

或者這樣：

for (int i = 0; i < n*n*n*n*n*n; i++) { 
    sum += i; 
}

爲O（n^6），即使有一個單一的環。

真正重要的是每個循環做了多少次迭代。

就你而言，很容易看出最內層循環的每次迭代都是O（1）。有多少次迭代？你需要多少次翻倍才能到達n？如果x是迭代次數，我們將在第一個x處退出循環，使得k = 2^x> n。你能解決這個問題嗎？

第二個循環的每次迭代都會這樣做，所以第二個循環的代價是迭代次數（這次更容易計算）乘以內部循環的代價。

第一個循環的每個迭代都會這樣做，所以第一個循環的代價是迭代次數（也很容易計數）乘以第二個循環的代價。

總的來說，運行時間是3個數字的乘積。你能找到他們嗎？

來源

2017-09-13 22:43:56 meriton

3個嵌套for循環的大O？

回答

相關問題