時間複雜度：while循環嵌套for循環[java]

所以我剛開始學習時間複雜度，我對它有一些「好的」把握，但是我對如何處理這段代碼有點困惑。我已閱讀其他帖子，但我只是很難抓住的東西，除非有人屠夫我不得不說。有點像一巴掌。時間複雜度：while循環嵌套for循環[java]

public int example(int[] array) { 

    int result = 15; 
    int i = array.length; 

    while(i > 1) 
    { 
     for(int x = 0; x < array.length;x++) 
     { 
     result+= 1; 
     result+=2*array[x]; 
     } 
     i = i/2; 
    } 
return result; 
}

好吧，所以我只計算算術運算。從我相信，糾正我，如果我錯了（可能是），

x ++發生n次。

結果+ = 1發生n次。

結果+ = 3 *陣列[X]發生2n倍

所有總共4N倍

和I = I/2發生LOGN倍

那麼正確的方程將是4nlogn ??

來源

2016-09-20 CabDude

爲什麼你認爲循環中的第二條語句執行的次數是前一次的兩倍？ – ChiefTwoPencils

我假設是因爲2個算術運算正在發生，但我想它只發生n次？ – CabDude

我現在看到你的邏輯了。 – ChiefTwoPencils

你在正確的軌道上4n*log(n)。但是，請注意，對於大時間複雜度，常量將被刪除，因此這將是O(n*log(n))。

由於大的O定義，常量被刪除：f(x)是O(g(x))如果f(z) <= c*g(z)對於所有的z>某個數字。這裏的關鍵是c，它可以是任何常數。即使你的f(x)是100x你仍然可以有c=200和g(x)仍然會更大。作爲一個方面說明，因爲我們可以將常量分解出來，所以在計算大O時間複雜度時，您不必計算每個操作的次數。你只需要看看循環。發生一次n次，其他log(n)次。所以它是O(n*log(n))。代碼可以在每個循環內執行1000次操作，或者它可以執行2次。由於常數是從我們的大O方程中分解出來的，所以這個數字並不重要。只有循環的數量和性質。

來源

2016-09-20 20:58:26 nhouser9

結果如何+ = 2 *數組[x]是n次而不是n次？ –

時間複雜度：while循環嵌套for循環[java]

回答

相關問題