big-o - 嵌套 for 循环的大 O 复杂度

Question

我对以下的复杂性感到困惑（在内部循环中执行的操作是在恒定时间内）：

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++)

Answer 1

当然O(n squared)，当然。两种情况的总结解释： 1 + 2 + ... + n 是n(n+1)/2，也就是说，(n squared plus n) / 2（在 big-O 中，我们删除了第二个较小的部分，所以我们剩下 n 平方 / 2 当然是O(n squared)）。

Answer 2

你是对的，那些嵌套循环仍然是 O(n^2)。实际操作数接近 (n^2)/2，在丢弃常数 1/2 因子后，为 O(n^2)。