确定一个给定的算法

的大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

确定一个给定的算法

回答

相关问题