嵌套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而言,我们执行代码的次数是多少？

好吧,从数学角度来说,我们可以说它的执行时间不会超过n²次,这给我们带来了最糟糕的情况,因此我们的O(n²)的Big-Oh界限也是如此.(有关我们如何在数学上说这看Power系列的更多信息)

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 2> = n(由于n = 0或1的情况,不严格地大于n),假设n总是整数.

实际的Big O复杂性与我刚才所说的略有不同,但这是它的要点.实际上,Big 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).另请参见此处具有相同运行时的非常类似的示例.

Answer 4

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

\n

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

\n

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

\n

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

\n

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

\n

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

\n

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

\n

1 + 2 + 3 + \xe2\x80\xa6 + n

\n

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

\n

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

\n

= O(n^2)

\n

\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94\xe2\x80\x94

\n

另外，请看看这些

\n

\n
1. /sf/answers/5026365011/
\n
2. /sf/answers/5007620201/
\n
3. /sf/answers/4887531491/
\n
4. /sf/answers/5043277781/
\n
5. /sf/answers/5043285341/
\n

\n