我的计算机科学 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
我只是不确定我是否做得正确。有人可以解释如何评估这样的代码和/或确认我的答案吗?