什么是嵌套循环的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）呢？
是的，它仍然是O（n ^ 2），它有一个较小的常数因子，但是这并不影响O符号。
是。 回顾一下Big-O： O（f（n））的定义，定义为运算时间T（n） ≤kf（n）对于某个常数k 。 在这种情况下，步数将是（n-1）+（n-2）+ … + 0 ，其重新排列为0到n-1之和; 这是
T（n）=（n-1）（（n-1）+1）/ 2 。
重新排列，你可以看到T（n）将总是≤1/ 2 （n2 ）; 根据定义，因此T（n）= O（n 2） 。
如果忽略System.out.println，则为N平方。 如果你认为它的输出时间是线性的（当然这可能不是这样），我怀疑你会以O（（N ^ 2）* logN）结束。
我提到这并不挑剔，但是要指出，在处理复杂性时，不仅需要考虑明显的循环，还需要考虑所谓的复杂性。
是的，这将是N平方。 如果我没有弄错的话，实际的步数将是1到N之和，即.5 *（N-1）^ 2。 大O只考虑最高的无常数，因此，这仍然是N平方。
如果你有N = 10，你的迭代将是：10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1。 （这是：十次迭代加九次迭代加八次迭代…等）。
现在，你需要find多less次你可以得到一个N（在这个例子中是10）：
1：（10），2：（9 + 1），3：（8 + 2），4：（7 + 3），5：（6 + 4） 这是5次…并rest5次迭代。
现在你知道你有五十+5：
10（5）+5
就f（n）（或N）而言，我们可以很容易地看到这将是：
f（n）= n（n / 2）+ n / 2 =（n ^ 2）/ 2 + n / 2 =（n ^ 2 + n）/ 2 …这正是这些嵌套循环的复杂性。
但是，考虑到大O的渐近行为，我们可以去掉单个n和分母f（n）的重要值。
结果：O（n ^ 2）
从内部循环到外部循环开始的AFAIL是计算嵌套循环复杂度的充分方法。 
