带条件嵌套循环的渐近分析(j=i+1)
Asymptotic analysis of nest loop with condition (j=i+1)
我试图理解此页面上大 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，内部循环会 运行 for N。如果i=0，那么j=1，那么内循环的迭代次数应该是N-1。我明白为什么这个循环的复杂度是O(n^2)。我不明白的是为什么内循环以 N 迭代次数开始，而不是 N-1.
这个 Big-O 是 O(n^2)。
外循环是O(n)，内循环是O(n - 1)。
所以有效时间复杂度是O(n^(n - 1)) = O(n^2 - n)。
现在n的值越大，n^2的值就会明显高于n，最终结果将取决于n^2
因此时间复杂度为O(n^2)
您的 link 有一点小错误。实际上，内部循环从 N-1 次迭代而不是 N 开始，但结果保持不变。
从第一个错误开始，他们在每次迭代中都错过了 1 个错误。他们忘记了 +1 我猜 j=i+1。
我试图理解此页面上大 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，内部循环会 运行 for N。如果i=0，那么j=1，那么内循环的迭代次数应该是N-1。我明白为什么这个循环的复杂度是O(n^2)。我不明白的是为什么内循环以 N 迭代次数开始，而不是 N-1.
这个 Big-O 是 O(n^2)。
外循环是O(n)，内循环是O(n - 1)。
所以有效时间复杂度是O(n^(n - 1)) = O(n^2 - n)。
现在n的值越大，n^2的值就会明显高于n，最终结果将取决于n^2
因此时间复杂度为O(n^2)
您的 link 有一点小错误。实际上，内部循环从 N-1 次迭代而不是 N 开始，但结果保持不变。
从第一个错误开始，他们在每次迭代中都错过了 1 个错误。他们忘记了 +1 我猜 j=i+1。