0

我一直在搜索有关大 O 表示法的论坛并学到了很多东西。我的问题非常具体,我认为一个独特的案例将更好地帮助我理解大 O,我忽略了常量。

据我了解,如果循环遍历所有元素而不是 O(n)。

for(int i = 0; i < n; i++)
{   

}

如果一个循环遍历所有 n,在另一个遍历所有 n 的循环内,它乘以 n * n = n^2

for(int i = 0; i < n; i++)
{
    for(int j = 0; j < n; j++)
    {

    }
}

最后,如果一个循环后面跟着另一个遍历所有元素的循环,它是 n + n = 2n

for(int j = 0; j < n; j++)
{

}
for(int k = 0; k < n; k++)
{

}

我的问题直接进行了这些代码行

for(int i = 0; i < n; i++)
{             
    for(int j = 0; j < n; j++)    
    {

    }
    for(int k = 0; k < n; k++)
    {

    }
    for(int l = 0; l < n; l++)
    {
        for(int m = 0; m < n; m++)
        {

        }
    }

}

所以根据上面的规则,我计算大 O 为 n * (n + n + n * n),即 n^3 + 2n^2。那么这会使我的大 O(n^3)还是我的大 O 是 O(n^3 +2n^2)。我对这一切都错了吗?还是我在球场附近的某个地方?主要是我想弄清楚这些循环是否小于 O(n^4)。提前致谢。

4

1 回答 1

2

big-O 表示法用于表征算法的渐近行为,该算法取决于指示数据量的某个值 n,但与任何常数(例如处理器速度)无关。
在您的示例中,n^3 的增长速度比 2n^2 快,即对于较大的 n,与 n^3 相比,2n^2 可以忽略不计。因此,嵌套循环的渐近行为具有 O(n^3) 阶。

于 2013-04-03T05:05:58.877 回答