55

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

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

是O(n^2)吗？

4

9 回答 9

81

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

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

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

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

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

好吧，从数学上讲，我们可以说它执行不超过 n² 次，这给了我们最坏的情况，因此我们的 O(n²) 的 Big-Oh 界限。（有关我们如何在数学上这样说的更多信息，请查看Power Series）

Big-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=0 或 1 的情况），假设 n 始终是整数。

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

于 2009-02-09T00:20:41.287 回答
67

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

如果 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)

于 2014-11-08T00:09:17.753 回答
13

实际上，它是 O(n^2)。另请参见此处具有相同运行时的非常相似的示例。

于 2009-02-09T00:08:46.963 回答
3

在外循环的第 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 
于 2015-04-16T21:03:06.403 回答
3

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

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

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

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

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

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

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

1 + 2 + 3 + … + n

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

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

= O(n^2)

于 2022-02-16T17:26:20.353 回答
2

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

于 2019-10-26T08:03:29.487 回答
0

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

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

同样，外循环运行n次，每次迭代，内循环最多运行n次。因此，内循环迭代的总数最多为 n 2。这也在 O(n 2 ) 中。

于 2021-03-13T16:33:34.830 回答
-1

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

for n = 5 if i = 1 内部循环运行 1 次 1 = 1

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

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

if i = 4 内部循环运行 4 次 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)

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

于 2021-09-13T09:12:07.587 回答
-2

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

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

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

于 2014-04-29T10:20:19.493 回答