runtime - 大 Oh 符号和计算三嵌套 For 循环的运行时间

Question

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

我知道，就 n 而言，双嵌套 for 循环的运行时间通常为 n2，而三重嵌套的 for 循环的运行时间通常为 n3。

但是，对于代码看起来像这样的情况，运行时间会是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)2+1。假设这些项相乘，我们提取最高项来找到Big Oh，运行时间是n4，还是仍然遵循通常的n3运行时间？

我将不胜感激任何输入。非常感谢您提前。

Answer 1

你是对的，n*2n*4n2 = O(n4)。

三重嵌套循环仅意味着将有三个数字相乘以确定最终的大 O - 每个被乘数本身取决于每个循环执行的“处理”量。

在您的情况下，第一个循环执行 O(n) 操作，第二个循环执行 O(2n) = O(n) 并且内部循环执行 O(n2) 操作，因此总体 O(n*n*n2) = O(n4 )。