嵌套for循环的时间复杂度

Question

我需要计算以下代码的时间复杂度：

for (i = 1; i <= n; i++)
{
  for(j = 1; j <= i; j++)
  {
   // Some code
  }
}

是O(n^2)吗？

Answer 1

是的，嵌套循环是快速获得大 O 表示法的一种方法。

通常（但并非总是）一个循环嵌套在另一个循环中将导致 O(n²)。

想一想，对于 i 的每个值，内循环都会执行 i 次。
外层循环执行n次。

因此你会看到这样的执行模式：
1 + 2 + 3 + 4 + ... + n 次

因此，我们可以通过说它显然执行超过 n 次（下限）来限制代码执行次数，但就 n 而言，我们执行了多少次代码？

好吧，从数学上讲，我们可以说它执行的次数不会超过 n2 次，这给了我们最坏的情况，因此我们的 Big-Oh 界限为 O(n2)。 请参阅幂级数）

（有关如何用数学方法表达这一点的更多信息， Oh 并不总是准确地测量正在完成的工作量，但通常给出最坏情况的可靠近似值。

---

4年后编辑：因为这篇文章似乎获得了相当多的流量。 我想更全面地解释我们如何使用幂级数将执行绑定到 O(n²)

来自网站：1+2+3+4...+n = (n² + n)/2 = n²/2 + n /2。 那么我们如何将其转化为 O(n²) 呢？ 我们（基本上）说的是 n² >= n²/2 + n/2。 这是真的？ 让我们做一些简单的代数。

• 两边同时乘以2得到：2n²>=n²+n？
• 展开 2n² 可得：n² + n² >= n² + n？
• 两边减去n²可得：n²>=n？

应该清楚的是，假设 n 始终是整数，则 n² >= n（不是严格大于，因为 n=0 或 1 的情况）。

实际的 Big O 复杂度与我刚才所说的略有不同，但这就是它的要点。 实际上，大 O 复杂度询问是否存在一个常数，我们可以将其应用于一个函数，使其比另一个函数大，以获得足够大的输入（请参阅 维基百科页面）

Answer 2

解释这一点的一个快速方法是将其可视化。

如果 i 和 j 都从 0 到 N，在这种情况下很容易看出 O(N^2)

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

，它是：

O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O

这是 N^2 的 1/2，仍然是 O(N^2)

Answer 3

事实上，它是 O(n^2)。 另请参阅具有相同运行时的非常相似的示例此处< /a>.

Answer 4

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

for (int i = 1; i <= n; i++){  // outer loop
    for (int j = 1; j <= i; j++){  // inner loop
        // some code
    }
}

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

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

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

因此，在外循环的最后一次迭代 (i = n) 中，内循环执行n 次。

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

1 + 2 + 3 + … + n

= (n(n + 1) / 2) （自然数之和公式)

= (((n^2) + n) / 2)

= O(n^2)

——————

另外，请看一下这些

1. https://stackoverflow.com/a/71805214/17112163
2. https://stackoverflow.com/a/71537431/17112163
3. https://stackoverflow .com/a/69821878/17112163
4. https://stackoverflow.com/a/72046825/17112163
5. < a href="https://stackoverflow.com/a/72046933/17112163">https://stackoverflow.com/a/72046933/17112163

Answer 5

在外循环的第 1 次迭代（i=1）时，内循环将迭代 1 次
在外循环的第 2 次迭代（i=2）时，内循环将迭代 2 次
在外循环的第 3 次迭代（i=3）时，内循环将迭代 3 次

。

。

在外循环的最终迭代中（i=n），内循环将
迭代 n 次

，因此，内循环中的语句将被执行的总次数
等于从 1 到 n 的整数之和，即：

((n)*n) / 2 = (n^2)/2 = O(n^2) times 

Answer 6

是的，这个的时间复杂度是O(n^2)。

Answer 7

正如其他正确答案所示，最终的复杂度为 O(n²)。 主要是 O(n²/2)，归结为 O(n²)。 这就是为什么 /2 并不重要：

重要的是要理解时间复杂度不是指的是算法的速度，而是指速率 速度相对于 n变化。 变化率。

假设我们有两种算法：

• A 复杂度为 O(n²)
• B 复杂度为 O(n²/2)

对于输入大小 (n) 为 5，您可以像这样解决时间复杂度：

• 对于 A - O(n²) 为 25
• 对于 B - O(n²/2)，即 12.5

现在，对于大小为 10 的输入，您将解决复杂性，如下所示：

• 对于 A - O(n²)，即 100
• 对于 B - O(n²/2)，即 50

In无论哪种情况，输入大小加倍都会使运行时间增加四倍。 这意味着就时间复杂度而言，O(n²/2) 与 O(n²) 相同。 正如我所说，时间复杂度并不是衡量运行算法需要多长时间，而是衡量时间如何随着输入大小而变化。

Answer 8

我认为最简单的思考方法是这样的：

外部循环运行 n 次，并且对于这些迭代中的至少 n/2 次，内部循环至少运行 n/2 次。 因此，内循环迭代的总数至少为 n²/4。 也就是 O(n²)

类似地，外层循环运行 n 次，而在每次迭代中，内层循环最多运行 n 次。 因此，内循环迭代的总数最多为 n²。 这也是 O(n²) 的时间。

Answer 9

内部循环取决于外部循环，内部循环运行 I 次，这给了我

n = 5
如果 i = 1 内部循环运行 1 次 1 = 1

如果 i = 2 内部循环运行 2 次 1 + 2 = 3

如果 i = 3 内部循环运行 3 次 1 + 2 + 3 = 6

如果 i = 4 内部循环运行 4 times 1 + 2 + 3 + 4 = 10

if i = 5 内循环运行 5 次 1 + 2 + 3 + 4 + 5 = 15

从上面我们可以知道 n (n + 1) / 2

所以 O(n * (n+1))/2
= O(n2/2 + n/2)
= O(n2/2) + O(n/2)

我不擅长算法分析，所以请随时纠正我的答案。

Answer 10

首先，我们将考虑内部循环的迭代次数独立于外部循环索引值的循环。 例如：

 for (i = 0; i < N; i++) {
     for (j = 0; j < M; j++) {
         sequence of statements
      }
  }

外循环执行N次。 每次执行外循环时，内循环都会执行M次。 结果，内循环中的语句总共执行了N*M次。 因此，两个循环的总复杂度为 O(N2)。