嵌套for循环的时间复杂度

Question

嵌套for循环的时间复杂度

66

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

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

这是O(n^2)吗？

- yyy

3

这是一个嵌套循环，时间复杂度为 O(n^2)。 - Jay Conrod

1

我的问题并不完全是你链接的那个问题的副本，但它是一个常见的问题，所以我猜它以许多形式被问到。 - yyy

2

相关：如何找到一个算法的时间复杂度 - Bernhard Barker

1

这回答您的问题吗？嵌套循环的时间复杂度如何计算，其中内部循环的迭代次数由外部循环的当前迭代确定？（链接：https://dev59.com/NXRC5IYBdhLWcg3wP-n5） - Ashutosh

10个回答

93

一个快速解释的方法是通过可视化展示。

如果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的平方的1/2，仍然是O(N的平方)

- Krys Jurgowski

3

感谢您最终帮助我理解内部循环中j<=i条件如何导致1/2 N^2的结果。这一直困扰着我。您能解释一下为什么这仍然是O(N^2)吗？感谢您终于帮我理解了内层循环使用 j<=i 条件所导致的1/2 N^2结果。这一直是我的疑问。您能否解释一下，这为什么仍然算作O(N^2)呢？ - erstaples

2

由于摩尔定律，我们可以假设算法执行速度每18个月翻倍。因此，在分析算法时，我们可以忽略系数，只关注n的算法。基本上，O(n^2)在18个月内将变为O(1/2 n^2)。然而，随着n的增长，运行时间呈指数级增长，对于线性时间算法，它会随着n的增加而增长。 - Krys Jurgowski

1

所以，你的意思是计算大O符号时，1/2在1/2(n^2)中并不重要，这部分原因是系数随着时间的推移变得无关紧要？该术语的重要部分 - 再次以大O的术语来描述 - 是它是二次的，而不是它被减半的二次。 - erstaples

1

是的，完全正确。此外，运行时间呈指数增长。当您的数据从100个点增加到10,000个点，再到10,000,000个点时，您的算法变得无法使用，因为运行时间无法随着输入的增加而扩展。http://www.cl.cam.ac.uk/~djg11/speedo/run1-plot.png - Krys Jurgowski

14

确实，它的时间复杂度是O(n^2)。此外，这里有一个非常相似的例子，其运行时间也是O(n^2)。

- Chris Bunch

8

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

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

另外，请看一下这些：

- Deepthi Tabitha Bennet

4

On the 1st iteration of the outer loop (i = 1), the inner loop will iterate 1 times On the 2nd iteration of the outer loop (i = 2), the inner loop will iterate 2 time On the 3rd iteration of the outer loop (i = 3), the inner loop will iterate 3 times
.
.
On the FINAL iteration of the outer loop (i = n), the inner loop will iterate n times

So, the total number of times the statements in the inner loop will be executed will be equal to the sum of the integers from 1 to n, which is:

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

- user2831683

2

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

- Saykat

2

正如其他正确的答案所示，结果的复杂度是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

现在，对于输入大小为n=10，你可以这样计算复杂度：

对于A - O(n²)，结果为100
对于B - O(n²/2)，结果为50

无论哪种情况，输入大小加倍会使运行时间增加四倍。这意味着就时间复杂度而言，O(n²/2)与O(n²)相同。正如我所说，时间复杂度不是算法运行所需的时间，而是该时间相对于输入大小的变化。

- Emmanuel

0

我认为最容易理解的方法是这样的：

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

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

- Matt Timmermans

-1

内部循环依赖于外部循环，内部循环运行I次，这给了我

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

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

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

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

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

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

- kta

-2

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

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

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

- napendra

8

你能否写出证明N*M = N^2的过程？以便更好地理解它。 - eaglei22

1

我很好奇为什么我们可以进行这种简化。 - Robin Andrews

这似乎是正确的答案。其他答案假设两个循环具有相同的n？ - nate sire

那么它的时间复杂度是O(n*m)，对吧？ - tamerlaha

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SauceMaster · Accepted Answer

是的，嵌套循环是一种快速获得大O符号表示的方式之一。

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

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

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

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

好吧，从数学上讲，我们可以说它最多会执行n²次，给出我们的最坏情况和Big-Oh边界为O(n²)。（有关如何在数学上表达这一点的更多信息，请参见幂级数）

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始终是整数。

实际的大O复杂度略有不同，但这就是其要点。实际上，大O复杂度询问是否存在一个常数可应用于一个函数，使它比另一个函数更大，对于足够大的输入（请参阅维基百科页面）。