嵌套 for 循环的 Big-O 复杂度
我对以下内容的复杂性感到困惑（内部循环内执行的操作是在恒定时间内执行的）：
for(int i=0; i<n; i++)
for(int j=i; j<n; j++)
这是 O(n^2) 还是 O(n)？我算O(n^2)。有什么想法吗？
以下内容也让我感到好奇：
for(int i=0; i<n; i++)
for(j=0; j<i; j++)
I'm confused about the complexity of the following (the operation performed inside the inner loop is in constant time):
for(int i=0; i<n; i++)
for(int j=i; j<n; j++)
is this O(n^2) or O(n)? I figure O(n^2). Any ideas?
also the following makes me curious:
for(int i=0; i<n; i++)
for(j=0; j<i; j++)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
当然，绝对是
O(n squared)。两种情况的简要说明：1 + 2 + ... + n 为n(n+1)/2，即(n 平方加 n) / 2（在 big-O 中，我们删除了第二个较小的部分，因此我们剩下 n 平方 / 2，这当然是O(n squared)）。Definitely
O(n squared), of course. Summary explanation for both cases: 1 + 2 + ... + n isn(n+1)/2, that is,(n squared plus n) / 2(and in big-O we drop the second, lesser part, so we're left with n squared / 2 which is of courseO(n squared)).你是对的，那些嵌套循环仍然是 O(n^2)。实际操作次数接近 (n^2)/2，在丢弃常数 1/2 因子后，为 O(n^2)。
You are correct, those nested loops are still O(n^2). The actual number of operations is something close to (n^2)/2, which, after discarding the constant 1/2 factor, is O(n^2).