什么是嵌套循环的Big-O，其中内循环中的迭代次数由外循环的当前迭代确定？

Question

什么是嵌套循环的Big-O，其中内循环中的迭代次数由外循环的当前迭代确定？以下嵌套循环的Big-O时间复杂度是多少：for(int i = 0; i < N; i++) {     for(int j = i + 1; j < N; j++)     {         System.out.println("i = " + i + " j = " + j);     }}它还是O（N ^ 2）吗？

Answer 1

是的，它仍然是O（n ^ 2），它具有较小的常数因子，但这不会影响O表示法。

Answer 2

是。回想一下大-O的定义：O（F（N））由定义说，运行时间T（N） ≤ KF（n）的一些恒定ķ。在这种情况下，步数将是（n-1）+（n-2）+ ... + 0，其重新排列为0到n-1的和; 这是

T（n）=（n-1）（（n-1）+1）/ 2。

重新排列，你可以看到T（n）总是≤1/ 2（n²）; 根据定义，因此T（n）= O（n 2）。

Answer 3

如果忽略System.out.println，则为N平方。如果你假设它所花费的时间在它的输出中是线性的（当然它可能不是），我怀疑你最终得到O（（N ^ 2）* log N）。

我提到这不是挑剔，但只是要指出你在解决复杂性时不仅需要考虑明显的循环 - 你需要考虑你所称的复杂性。