n^3 嵌套 For 循环的大 O 表示法
考虑以下代码：
for ( int j = 0; j < 2n; j++)
{
for ( int k = 0; k < n^3; k += 3)
sum++;
}
复杂度是O(n^2)吗？ for 循环中的 n^3 是否影响 LARGE N 的表示法？
Considering the following code:
for ( int j = 0; j < 2n; j++)
{
for ( int k = 0; k < n^3; k += 3)
sum++;
}
Is the complexity O(n^2)? Does the n^3 in the for loop affect the Notation for LARGE N?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
O(N^4)
sum++ 被调用 2*n*(n^3)/3 次。
O(N^4)
sum++ is called 2*n*(n^3)/3 times.
如果只考虑内层循环，它会执行 N^3 次，
外层循环会使内层循环执行 N 次，所以总复杂度 = N * N^3 = N^4
if you only consider the inner loop, it gets executed N^3 times
the outer loop makes the inner one execute N times, so total complexity = N * N^3 = N^4
外循环有 O(2n) 次操作。
内循环有 O(n^3) 次操作。
总而言之，该程序的复杂度为 O(n)*O(n^3) = O(N^4)。
The outer loop has O(2n) operations.
The inner loop has O(n^3) operations.
Together, the program has O(n)*O(n^3) = O(N^4).
确切的迭代次数和增长复杂度的顺序可以正式推断：
The exact number of iterations and the order of growth complexity can be inferred formally: