我需要幫助瞭解如何找到代碼段的Big-Oh

我的計算機科學II最後是明天，我需要一些幫助瞭解如何找到代碼段的Big-Oh。我搜索了互聯網，並沒有找到任何我需要了解它的例子。我需要幫助瞭解如何找到代碼段的Big-Oh

這是我們從樣本最後一個問題：

for(int pass = 1; i <= n; pass++) 
{ 
    for(int index = 0; index < n; index++) 
     for(int count = 1; count < n; count++) 
     { 
      //O(1) things here. 
     } 
    } 
}

我們應該找到該算法的順序（big-OH）。

我認爲，這將是爲O（n^3），這裏是我是如何來到這個結論

for(int pass = 1; i <= n; pass++) // Evaluates n times 
{ 
    for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
     for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
     { 
      //O(1) things here. 
     } 
    } 
} 
// T(n) = (n) + (n^2 + n) + n^3 
// T(n) = n^3 + n^2 + 2n 
// T(n) <= c*f(x) 
// n^3 + n^2 + 2n <= c * (n^3) 
// O(n) = n^3

我只是不知道如果我做正確。有人可以解釋如何評估這樣的代碼和/或確認我的答案嗎？

來源

2013-05-05 chutch1122

你的回答是正確的，但是你爲每個循環計算的迭代次數不是。第一次和第二次迭代次數都是'n'次，第ird重複「n - 1」次。顯然這並不影響結果。 – 2013-05-05 22:29:58

如果您必須使用O（n^3）算法來解決現實世界的問題，那麼情況會非常糟糕。 – john 2013-05-05 22:32:04

@john：這也取決於很多情況和數量'n' :-) – deepmax 2013-05-05 22:34:16

是的，它是O(n^3)。但是：

for(int pass = 1; pass <= n; pass++) // Evaluates n times 
{     //^^i should be pass 

    for(int index = 0; index < n; index++) //Evaluates n times 
     for(int count = 1; count < n; count++) // Evaluates n-1 times 
     { 
      //O(1) things here. 
     } 
    } 
}

由於有三個層的嵌套的for循環，嵌套循環將被評估n *n * (n-1)次，每次操作中的最內側的for循環花費O（1）時間，所以在總你有n^3 - n^2恆定按照增長的順序是O(n^3)。

如何衡量大O符號增長級很好的總結可以在這裏找到：

Big O Notation MIT

從上述文件中引用部分：

嵌套循環
for I in 1 .. N loop 
    for J in 1 .. M loop 
     sequence of statements 
    end loop; 
end loop; 
外循環執行N次。每次執行外循環時，內循環執行M次。結果，內循環中的語句總共執行N * M個次。因此，複雜度是O（N * M）。在內環的停止條件是J <N而不是的J <M（即，內環也執行N次）的常見特例中，兩個環的總複雜度爲O（N^2）。

類似的理由可以適用於你的情況。

來源

2013-05-05 22:30:54 taocp

好吧，爲什麼第二個for循環只評估n次索引 chutch1122 2013-05-05 22:36:44

@ chutch1122我們計算的是嵌套for循環內執行的操作數，而不是for循環的條件得到評估。因此，即使你說的是正確的，但for循環的主體只能執行n次。 – taocp 2013-05-05 22:40:28

@ chutch1122您輸入循環體的次數，而不是評估'index john 2013-05-05 22:40:36

你是絕對正確的。你的例子是O（n^3）。

要查找任何代碼段的大哦運行時間，您應該考慮一段代碼執行O（1）次操作的次數。

讓我簡化你的例子給的這一個更好的主意：

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
    { 
     //O(1) things here. 
    } 
}

在上述情況下，內循環運行N次外循環的每次運行。而你的外部循環也運行n次。這意味着你正在做n件事，n次。使它成爲O（n^2）。

另一件需要注意的事情是大哦是一個上限。這意味着當你有一個大的輸入時，你應該總是考慮代碼將會發生什麼（在你的情況下，大的值爲n。這個事實的另一個含義是常數的乘法或加法對Big因爲O（N *（2N））= O（N^2）

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < 2*n; count++) // Runs 2*n times 
    { 
     //O(1) things here. 
    } 
}

此代碼的大哦運行時間也爲O（n^2）

：噢結合例如。另外檢查一下：http://ellard.org/dan/www/Q-97/HTML/root/node7.html

來源

2013-05-05 22:40:26 Sid

我需要幫助瞭解如何找到代碼段的Big-Oh

回答

相關問題