对嵌套循环复杂度的疑惑
Doubts about the complexity of a nested loop
我对这个内循环的复杂性的回答有疑问：
for(i=0;i<n;i++){
for(j=i+1;j<n;j++)
第一个循环将迭代 n-1 次，我认为内部循环应该迭代 (n-1)*(n-1-j) 次。
在最坏的情况下，应该总是少于 n^2 次迭代但多于 n 次迭代，
所以我不确定复杂度是 O(n) 还是 O(n^2)。我的答案是 O(n^2) 但我不确定。
时间复杂度为O(n^2)，因为O(n*(n-1))仍然是O(n^2)。
我对这个内循环的复杂性的回答有疑问：
for(i=0;i<n;i++){
for(j=i+1;j<n;j++)
第一个循环将迭代 n-1 次，我认为内部循环应该迭代 (n-1)*(n-1-j) 次。
在最坏的情况下，应该总是少于 n^2 次迭代但多于 n 次迭代， 所以我不确定复杂度是 O(n) 还是 O(n^2)。我的答案是 O(n^2) 但我不确定。
时间复杂度为O(n^2)，因为O(n*(n-1))仍然是O(n^2)。