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

Question

什么是以下的嵌套循环的大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²）

Answer 3

有n值的平方，如果你忽略的System.out.println。如果假设由所花费的时间将在其输出（其很可能不是当然）是线性的，我怀疑你结束了O（（N ^ 2）*日志N）。

我提到这一点并不挑剔，只是要指出的是，你不只是需要采取明显的循环考虑制定复杂的时候 - 你需要看看你叫什么，以及复杂

Answer 4

是，这将是N的平方。的实际步数将1到N，其为0.5 *之和（N - 1）^ 2，如果我没有记错。大O只考虑了最高exponant和没有常数，因此，这是静像N的平方。

Answer 5

如果你有N = 10，则迭代将是：10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1。 （这是：十次迭代加9次迭代加八次迭代...等）。

现在，你需要寻找到（在本例中10）另外，你可以有多少次得到N：

1：（10），2：（9 + 1），3：（8 + 2），4：（7 + 3），5：（6 + 4）。这是5倍...和搁置5次迭代。

现在你知道你有五个几十+ 5：

10（5）+ 5

在F（N）（或N），我们可以很容易地看到，这将是方面：

F（N）= N（N / 2）+ N / 2 =（N ^ 2）/ 2 + N / 2 =（N ^ 2 + N）/ 2 ...这是这些完全的复杂性嵌套循环。

不过，考虑到大O的渐近行为，我们可以摆脱的F（N）少显著价值，这是一个n和分母的。

结果：为O（n ^ 2）

Answer 6

AFAIL，正从内部循环通过外部的开始是用于嵌套循环复杂度计算适当的方式。