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

是的。 回想一下 Big-O 的定义：O(f(n)) 根据定义，运行时间 T(n) ≤ kf(n) em> 对于一些常数k。 在这种情况下，步数将为(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

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

我提到这一点并不是为了挑剔，只是想指出，在计算复杂性时，您不仅需要考虑明显的循环 - 您还需要考虑您所调用的复杂性。

Answer 4

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

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

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

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

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

。
。
。

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

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

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

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

N - 1 + N - 2 + N - 3 + … + 2 + <代码>1 + <代码>0

= <代码>0 + <代码>1 + <代码>2 + … + N - 3 + N - 2 + N - 1

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

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

= (N - 1)(N) / 2

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

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

——————

另外，请看看这些

1. https://stackoverflow.com/a/71805214/17112163
2. https://stackoverflow.com/a/71146522/17112163
3. https://stackoverflow.com/a/69821878/17112163
4. https://stackoverflow .com/a/72046825/17112163
5. https://stackoverflow.com/a/72046933/17112163

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)

Answer 6

是的，它是N平方。 如果我没记错的话，实际步数是 1 到 N 的总和，即 0.5*(N - 1)^2。 Big O 只考虑最高指数而不考虑常数，因此，这仍然是 N 平方。

Answer 7

AFAIL，从内循环开始到外循环是计算嵌套循环复杂性的充分方法。

Answer 8

对于给定的程序：

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        println(...);

考虑 n = 3：

i 的值为 0、1 和 2。

For i = 0: println will execute 3 times
for i = 1: println will execute 2 times
for i = 2: println will execute 1 times

因此 println 函数将执行 3 + 2 + 1 次，即 n (n+1)/2 次。

因此 O(n(n+1)/2) = O(n^2)。