我需要帮助了解如何找到代码段的Big-Oh

Question

我的计算机科学II决赛是明天,我需要一些帮助,了解如何找到代码段的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

我只是不确定我是否正确地做到了.有人可以解释如何评估这样的代码和/或确认我的答案吗？

Answer 1

是的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 表示法衡量增长顺序的一个很好的总结可以在这里找到：

大 O 表示法 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 <Nin而不是J <M（即内循环也执行N次），两个循环的总复杂度为O(N^2)。

类似的理由也适用于您的情况。