嵌套for循环的Big-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++)

- Riz

---

http://en.wikipedia.org/wiki/Triangular_number - Anycorn

Answer 1

当然是 O(n squared)。两种情况的简要解释：1 + 2 + ... + n 等于 n(n+1)/2，也就是说，(n平方加上n) / 2 （在大O符号中我们舍去第二个较小的部分），因此我们得到了 n 平方 / 2, 当然是 O(n squared)。

- Alex Martelli

Answer 2

您说得对，这些嵌套循环仍然是O(n^2)。实际操作的次数接近于(n^2)/2，在舍弃常数因子1/2后，其时间复杂度为O(n^2)。

- Greg Hewgill