大O符号和计算三重嵌套for循环的运行时间

Question

4

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

我知道，双重循环的运行时间通常是n的平方，三重循环的运行时间通常是n的立方。

但是，在代码看起来像这样的情况下，运行时间会是n的四次方吗？

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³运行时间？

我希望得到任何意见。非常感谢您的帮助。

- Anonymous

我不明白为什么你会期望这个是O(n^3)？ - MK.

3个回答

2

正式地，使用Sigma符号表示，你可以得到如下公式： enter image description here

- Mohamed Ennahdi El Idrissi

0

这个问题可能与数学有关吗？

我的直觉和BrokenGlass一样，是O(n⁴)。

编辑：平方和和立方和可以很好地理解所涉及的内容。答案是O(n^4)：sum(a=0 to n) of (sum(b=0 to 2a) of (b^2))。内部总和等于a^3。因此你的外部总和等于n^4。

可惜，我认为你无法使用log代替n^4。不要紧。

- asoundmove

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BrokenGlass · Accepted Answer

你是正确的，n*2n*4n² = O(n⁴)。

三重嵌套循环意味着有三个数字相乘来确定最终的大O表示法 - 每个乘数本身取决于每个循环执行多少“处理”操作。

在你的例子中，第一个循环执行O(n)次操作，第二个循环执行O(2n) = O(n)次操作，内部循环执行O(n²)次操作，因此总体上O(n*n*n²) = O(n⁴)。