big-o - 什么是嵌套循环的 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)吗？

score 50 · Accepted Answer

50

是的，它仍然是 O(n^2)，它有一个较小的常数因子，但这不会影响 O 表示法。

于 2008-12-12T06:47:20.707 回答

score 30 · Accepted Answer

是的。回想一下 Big-O 的定义：O(f(n))根据定义表示某个常数k的运行时间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²)。

score 13 · Accepted Answer

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

我提到这并不是挑剔，而是要指出，在计算复杂性时，您不仅需要考虑明显的循环 - 您还需要查看所调用内容的复杂性。

score 4 · Accepted Answer

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

score 4 · Accepted Answer

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

现在，您需要在加法中找出可以得到 N 的次数（示例中为 10）：

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)

score 3 · Accepted Answer

对于给定的程序：

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)。

score 2 · Accepted Answer

2

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

于 2017-03-29T05:21:47.423 回答

7 回答 7