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

Question

以下嵌套循环的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).

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

Answer 4

让我们跟踪每次迭代中每个循环执行的次数。

\n

for (int i = 0; i < N; i++) {  // outer loop\n    for (int j = i + 1; j < N; j++) {  // inner loop\n        System.out.println("i = " + i + " j = " + j);\n    }\n}\n

\n

在外循环的第一次迭代中（i = 0），内循环执行N - 1次。

\n

在外循环的第二次迭代中（i = 1），内循环执行N - 2次。

\n

在外循环的第三次迭代中（i = 2），内循环执行N - 3次。

\n

.\n.\n.

\n

在外循环的第 1 次迭代中N - 2(i = N - 3)，内循环执行了2次。

\n

在外循环的第 1 次迭代中N - 1(i = N - 2)，内循环执行1一次。

\n

在外循环的最后 ( Nth) 次迭代 (i = N - 1) 中，内循环执行了0次。

\n

因此，该代码执行的总次数为

\n

N - 1+ N - 2+ N - 3+ \xe2\x80\xa6 + 2+ 1+0

\n

= 0+ 1+ 2+ \xe2\x80\xa6 + N - 3+ N - 2+N - 1

\n

将其代入自然数之和公式中，

\n

=(N - 1)((N - 1) + 1) / 2

\n

=(N - 1)(N) / 2

\n

=((N^2) - N) / 2

\n

= O(N^2)，假设System.out.println在恒定时间内执行O(1)。

\n

\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94

\n

另外，请看看这些

\n

\n
1. /sf/answers/5026365011/
\n
2. /sf/answers/4980256571/
\n
3. /sf/answers/4887531491/
\n
4. /sf/answers/5043277781/
\n
5. /sf/answers/5043285341/
\n

\n

Answer 5

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

现在，您需要计算加法有多少次可以得到 N（在我的示例中 N = 10）：

1:(10)、2:(9+1)、3:(8+2)、4:(7+3)、5:(6+4)。这是 5 次...并且仍然是 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...这正是这些嵌套循环的复杂性。

但是，考虑到 Big O 的渐近行为，我们可以去掉 f(n) 中不太重要的值，即单个 n 和分母。

结果：O(n^2)