logo标签列表

一个嵌套循环的时间复杂度是什么，其中内部循环的迭代次数由外部循环的当前迭代决定？答案是：Big-O。

big-onested-loops
71

以下嵌套循环的时间复杂度是多少： 

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)的时间复杂度吗？

请参见嵌套循环的时间复杂度。 - user456814
相关帖子 - 这个算法的最坏时间复杂度是多少？，嵌套for循环的时间复杂度和大O符号：具有依赖关系的嵌套for循环。 - RBT
8个回答
61

是的，它仍然是O(n^2)时间复杂度，虽然它有更小的常数因子，但这不影响O符号表示。

2
考虑到所提出的问题，你能说这个答案有点误导吗？他的问题明确要求：当内部循环的迭代次数由外部循环的当前迭代确定时，嵌套循环的大 O 是什么？他的例子仍然是 O(n^2)，但对于更广泛的问题，如果第二个循环是 n 的除法（仍然依赖于 n），你不会得到对数的 O(n)，而不是 n^2 吗？我只是一个学生，如果我错了，请指出。 - webfish
1
不：O（n log n）需要：for（int j = n; j> 0; j / = 2）[这是一个不同的域：j = n到n / 2]。而循环是i = 0到N和j = i + 1到N，两者仍在线性域中处理，因此：O（n）* O（n）= O（n ^ 2） - NeoH4x0r
32
是的。回想一下Big-O的定义：O(f(n))的定义是说运行时间T(n) ≤ kf(n)，其中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²)。
13

如果忽略System.out.println，时间复杂度将是N的平方。假设该操作的时间与其输出成线性关系（当然可能不是这样），我认为最终的时间复杂度将是O((N^2) * log N)。

我提到这个并不是为了挑剔，而是要指出，在计算复杂度时，你不仅需要考虑明显的循环，还需要考虑所调用函数的复杂度。

你能告诉我T(n)是什么吗？ - CodyBugstein
@Imray：很抱歉，我不确定你的意思。 - Jon Skeet
T(n)是确切的执行次数，可以总结/简化为大O表示法中的某个内容。例如，T(n)可能是2n^2 + 4n + 8等等... - CodyBugstein
@Imray：好的-在这种情况下，它取决于您要计算的确切内容...指令数量？执行的循环体数量？（后者将是0 + 1 + ... + N-1，即N ^ 2-N IIRC。 - Jon Skeet
我尝试了点赞，但系统显示无法接受。 - QuentinUK
显示剩余2条评论
7

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

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），内部循环不执行。
因此，此代码执行的总次数为 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://dev59.com/P0bRa4cB1Zd3GeqPxzDW#71805214
  2. https://dev59.com/iXRB5IYBdhLWcg3wv5o_#71146522
  3. https://dev59.com/iGoMtIcB2Jgan1znlqyc#69821878
  4. https://stackoverflow.com/a/72046825/17112163
  5. https://dev59.com/AIfca4cB1Zd3GeqPnMEb#72046933
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：
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)
现在，您需要在加法中找出可以得到N（例如中的10）的次数：您是如何想到这个的？抱歉，我的数学不好。 - Kid
4
是的，这将是N的平方。实际步骤数量将是1到N的总和，即0.5*(N-1)^2，如果我没有弄错的话。大O符号只考虑最高次幂而不考虑常数因子，因此，这仍然是N的平方。
你只是差了一点 - 从1到n的总和是n*(n+1)/2，或者.5n^2+.5n，这显然是O(n^2)。 - user57368
3
AFAIL，从内循环到外循环开始是计算嵌套循环复杂度的适当方法。enter image description here
3

对于给定的程序：

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)。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接