time-complexity - 带条件嵌套循环的渐近分析(j=i+1)

Question

我试图理解此页面上大 O 的示例:http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

for (i = 0; i < N; i++) {
   for (j = i+1; j < N; j++) {
      sequence of statements }
}

我不明白如果 i=0，为什么内部循环会运行 N。如果i=0，那么j=1，那么内循环的迭代次数应该是N-1。我明白为什么这个循环的复杂度是 O(n^2)。我不明白的是为什么内部循环以 N 次迭代开始，而不是 N-1。

Answer 1

您的链接有一点错误。实际上，内部循环从 N-1 次迭代而不是 N 开始，但结果保持不变。

从第一个错误开始，他们在每次迭代中都会错过 1 个错误。我猜他们忘记了 j=i+1 +1。