什么是嵌套循环的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表示法.

是.回想一下大-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).

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

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