嵌套顺序循环的大0符号

Question

我一直在论坛上搜索大0符号，并学到了不少东西。我的问题很具体，我认为一个特例能更好地帮助我理解大0，我忽略了常数。

根据我的理解，如果一个循环遍历所有元素，那么它就是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。那么这个是0 (n^3)还是0 (n^3 +2n^2)我做错了吗?还是说我差不多是对的?我主要是想弄清楚这些循环是否小于O(n^4)

Answer 1

大o符号用于描述算法的渐近行为，该行为依赖于表示数据量的某个值n，但与任何常数(例如处理器速度)无关。
在你的例子中，n^3比2n^2增长得快，也就是说，对于较大的n，与n^3相比，2n^2可以忽略。因此，嵌套循环的渐近行为为O(n^3)阶。