大O操作數

你如何計算每行代碼將要執行的操作次數。大O操作數

例子。

Algorithm find2D (A,x) 
    arrLength = A.length 
    for j <- 1 to arrLength – 1 do 
     for k <- 1 to arrLength – 1 do 
       if A[j][k] = x then 
        return true 
      increment k 
    increment j 
return false

我想出了這個僞代碼。所以我不確定如何計算每行代碼所需的操作次數。

所以，像第一個循環將是1 + n操作，因爲您必須設置j，比較j到arrLength - 1，它會循環n-1次。這樣就給你n-1 + 1 + 1這是n + 1的操作。

因此，對於第二個循環，即使其嵌套，它也是同樣的東西。

我對A[j][k] = x比較有點困惑，會有多少操作。

謝謝。

來源

2011-01-20 Matt

比較通常被認爲是1點的操作，並且因爲你在陣列中與所有其他項目進行比較的每個項目該比較將被稱爲N^2倍（最壞情況）。 – Lithium 2011-01-20 21:28:15

大哦是漸近的，所以你不應該關心「1 + n」中的「1」。

如果你正在尋找的是代碼的大哦分類，簡單地認爲你有兩個迴路，一個嵌套在另一個裏面，每一個循環做每件操作的一些常數。然後內部循環爲O（n），外部循環執行內部循環n次，所以外部循環爲O（n^2）。那麼整個函數是O（c + n^2），其中c是來自外部循環周圍代碼的常量操作數。由於Big-Oh漸近，c消失，你的函數是O（n^2）。

如果你想計算的代碼需要操作的確切數量，你可能需要建立你所使用的abstract machine。

希望這會有所幫助。

來源

2011-01-20 21:31:52 William

一般的經驗法則是：

對於每次循環數組中的每個元素，以N

乘以對於每個您分割陣列中的兩個重複的時間，通過對數乘以（ N）

由於您在整個數組上有兩個嵌套循環，因此您是O（N^2）。

計算常數因子是棘手的，它依賴於語言，編譯器和硬件的細節。基本上只需要憑經驗工作。

來源

2011-01-20 21:23:18

就大O而言，你應該選擇你要計算的操作，最常見的是原子操作。在這種情況下，它是兩個循環內部的比較。您不需要計算循環迭代的循環次數，只需計算在最壞情況下最內部執行的次數。外環爲n-1，內環爲n-1，總共爲O(n^2)。

來源

2011-01-20 21:26:09 NOtherDev

回答

相關問題