我的计算机科学 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
我只是不确定我是否做对了。有人可以解释如何评估这样的代码和/或确认我的答案吗?
最佳答案
是的,是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 表示法衡量增长顺序的一个很好的总结可以在这里找到:
上述文件的引用部分:
Nested loops
for I in 1 .. N loop for J in 1 .. M loop sequence of statements end loop; end loop;
The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the complexity is O(N * M). In a common special case where the stopping condition of the inner loop is
J <N
instead ofJ <M
(i.e., the inner loop also executes N times), the total complexity for the two loops is O(N^2).
类似的理由也适用于您的案例。
关于c++ - 我需要帮助来理解如何找到代码段的 Big-Oh,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16389748/