確定一個給定的算法

的大O我給這個算法（僞代碼，不以任何特定語言）：確定一個給定的算法

foo1(l,m,n){ 
    for (i = 1; i < l, i++){ 
     for(j = 1; j < m ; j++){ 
      for (k = 1; k < n; k++){ 
      //Constant time inner loop 
      } 
     } 
    } 
}

我試圖找到的時候，他內環運行數尊重l，m，和n併爲其提供了一個功能。我也試圖找出算法的大O符號。

看着算法，我在想內層循環會運行l * m * n次。我想出了這個，因爲例如，如果l，m，n分別是3，6，9，那麼內部循環將運行（9 * 6 * 3）次。因此，將返回的次數函數內循環運行會是這樣的：

f = l*m*n

現在大O就是我與（不一定有這個問題）艱難，但我希望得到一些進一步瞭解如何解決大O問題以最佳地確定算法的正確大O.

對於這個特定的情況，我在想大O會是n^3，但那只是基於猜測而已。我該如何去弄清楚這個問題實際上是什麼，更普遍的是我可能遇到的其他算法？

來源

2014-09-29 mufc

這將是O（l * m * n）。如果對'l'和'm'的值有約束使它們漸近地等於'n'，那麼就可以將它簡化爲O（n^3）。 – 2014-09-29 16:22:02

既然看起來你想要知道所有關於'big-o'表示法，而不是任何特殊的問題，我認爲這個問題太大了，不適合SO。投票結束。 – axiom 2014-09-29 17:06:57

你正處在理解big-O的正確軌道上。上述僞代碼確實有0（1米 n）的複雜性正如你可能找一些參考，我想，你看看上堆棧溢出本身以下真棒職位：

Plain English explanation of Big-O

在我看來，這是讓你開始使用Big-O概念的最佳指南之一。

如果您深入探究 this MIT Lecture。這將肯定會爲您詳細介紹Big-O概念。我認爲這兩個參考文獻將清除您的許多概念，並且一定會幫助您建立堅實的理解。

快樂傾斜！

來源

2014-09-29 18:46:40 anshuman

非常感謝。正是我需要的。 – mufc 2014-09-29 18:51:16

確定一個給定的算法

回答

相關問題