Big Oh 表示法和计算三重嵌套 For 循环的运行时间
在计算机科学中,对于计算机科学家来说,了解如何计算算法的运行时间以优化代码非常重要。我向你们计算机科学家提出一个问题。
据我了解,就 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。假设这些项相乘,我们提取最高项来找到大哦,运行时间是n4,还是仍然遵循通常的运行时间n3 ?
我将不胜感激任何意见。预先非常感谢您。
In Computer Science, it is very important for Computer Scientists to know how to calculate the running times of algorithms in order to optimize code. For you Computer Scientists, I pose a question.
I understand that, in terms of n, a double-nested for-loop typically has a running time of n2 and a triple-nested for-loop typically has a running time of n3.
However, for a case where the code looks like this, would the running time be n4?
x = 0;
for(a = 0; a < n; a++)
for(b = 0; b < 2a; b++)
for (c=0; c < b*b; c++)
x++;
I simplified the running time for each line to be virtually (n+1) for the first loop, (2n+1) for the second loop, and (2n)2+1 for the third loop. Assuming the terms are multiplied together, and we extract the highest term to find the Big Oh, would the running time be n4, or would it still follow the usual running-time of n3?
I would appreciate any input. Thank you very much in advance.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
![扫码二维码加入Web技术交流群](/public/img/jiaqun_03.jpg)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
你是对的,n*2n*4n2 = O(n4)。
三重嵌套循环仅意味着将三个数字相乘以确定最终的 Big O - 每个被乘数本身取决于每个循环执行的“处理”量。
在您的情况下,第一个循环执行 O(n) 操作,第二个循环执行 O(2n) = O(n) ,内部循环执行 O(n2) 操作,因此总体 O(n* n*n2) = O(n4)。
You are correct, n*2n*4n2 = O(n4).
The triple nested loop only means there will be three numbers to multiply to determine the final Big O - each multiplicand itself is dependent on how much "processing" each loop does though.
In your case the first loop does O(n) operations, the second one O(2n) = O(n) and the inner loop does O(n2) operations, so overall O(n*n*n2) = O(n4).
正式地,使用 Sigma 表示法,您可以获得:
Formally, using Sigma Notation, you can obtain this:
这可能是一个数学问题吗?
我的直觉,就像 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。没关系。
Could this be a question for Mathematics?
My gut feelings, like BrokenGlass is that it is O(n⁴).
EDIT: Sum of squares and Sum of cubes give a pretty good understanding of what is involved. The answer is a resounding O(n^4): sum(a=0 to n) of (sum(b=0 to 2a) of (b^2)). The inner sum is congruent to a^3. Therefore your outer sum is congruent to n^4.
Pity, I thought you might get away with some log instead of n^4. Never mind.