大O:哪个更好？

Question

我是Big-O符号的新手,所以我需要一些建议.假设我可以选择两种算法:一种是在一行中有几个for循环,或者是一个有三次嵌套for循环的算法.例如,一个结构类似于:

    for(int i = 0; i < a.length; i++)
    {
       // do stuff
    }

    for(int i = 0; i < b.length; i++)
    {
       for(int j = 0; j < c.length; j++)
       {
          // do something with b and c
       }
    }

    for(int i = 0; i < d.length; i++)
    {
       // do stuff
    }

另一种结构是这样的:

for(int i = 0; i < a.length; i++)
{
   for(int j = 0; j < b.length; j++)
   {
      for(int k = 0; k < c.length; k++)
      {
         // do stuff
      }
   }
 }

这些例子似乎不太实际,但我想我只是想说明我的真实问题:每种方法的大O符号是什么,并且具有3个嵌套循环的算法总是比具有许多两次嵌套循环的算法效率低(但不是3)？

Answer 1

什么是每种方法的大O符号

具有n个步骤的循环的大O嵌套在具有m个步骤的循环中O(n * m).具有n个步骤的循环的大O然后是具有m个步骤的循环的大O是O(n + m) = O(max(n,m)).

所以你的第一种方法是O( max(a.length, b.length * c.length, d.length)),第二种方法是O( a.length * b.length * c.length).哪一个更好取决于d.length是大于还是小于a.length * b.length * c.length.

并且具有3个嵌套循环的算法总是比具有许多两次嵌套循环(但不是3个)的算法效率低吗？

这取决于每个循环相对于另一个循环的步数.如果所有循环具有相同的步数,则3个嵌套循环将始终比2个嵌套循环更差.

Answer 2

不必要.使用a,b和c来表示变量,第一个例子是O(a + b*c + d),第二个例子是O(a*b*c).可能后者更糟糕,但它在很大程度上取决于这里的变量 - 在第一个例子中d可能是最重要的变量,而这将使得与第二个变量相比很难 - 除非我们假设第二个没有'有一个d因子(比如,某种优化)

此外 - 三个循环并不一定意味着效率较低,尽管通常情况如此.if外循环中的语句可能导致内循环不运行,这可能意味着O(n ²),尽管有三个嵌套循环.有时算法的构造似乎是一回事,但是通过更好的分析,我们发现虽然它看起来像是O(n ³),但它实际上服从O(n ²).