Big Oh表示法和计算三嵌套For循环的运行时间

Question

在计算机科学中,计算机科学家知道如何计算算法的运行时间以优化代码非常重要.对于你的计算机科学家,我提出了一个问题.

我理解,就n而言,双嵌套for循环通常具有n ²的运行时间,并且三嵌套for循环通常具有n ³的运行时间.

但是,对于代码如下所示的情况,运行时间是否为n4？

x = 0;
for(a = 0; a < n; a++)
    for(b = 0; b < 2a; b++)
        for (c=0; c < b*b; c++)
            x++;

我将每一行的运行时间简化为第一个循环的虚拟(n + 1),第二个循环的(2n + 1),以及第二个循环的(2n)² + 1.假设这些术语相乘,并且我们提取最高项以找到Big Oh,那么运行时间是n ⁴,还是它仍然会遵循通常的n ³运行时间？

我很感激任何意见.非常感谢你提前.

Answer 1

你是对的,n*2n*4n ² = O(n ⁴).

三重嵌套循环仅意味着将有三个数字相乘以确定最终的大O - 每个被乘数本身取决于每个循环的"处理"程度.

在你的情况下,第一个循环执行O(n)操作,第二个循环执行O(2n)= O(n),内部循环执行O(n ²)操作,因此总体O(n*n*n ²)= O (n ⁴).