嵌套for循环的时间复杂度

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

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

是O（n ^ 2）吗？

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

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

考虑一下，对于i 的每个值，内部循环都会执行i次。外循环执行n次。

因此你会看到如下的执行模式：1 + 2 + 3 + 4 + … + n次

因此，我们可以通过说明它执行多于n次（下限）来限制代码执行的次数，但是根据n我们执行代码的次数是多less？

那么从math的angular度来说，我们可以说它的执行次数不会超过n2次，给我们一个最坏的情况，因此我们的O（n2）的Big-Oh界限。（欲了解更多关于我们如何用math的方式来说明Power系列的信息）

大哦并不总是精确地测量完成了多less工作，但是通常给出可靠的最坏情况的近似值。

4年后编辑：因为这个post似乎得到相当数量的stream量。我想更全面地解释我们如何使用幂级数来限制执行到O（n ^ 2）

从网站：1 + 2 + 3 + 4 … + n =（n 2 + n）/ 2 = n 2/2 + n / 2。那我们怎么把它变成O（n²）呢？我们（基本上）说的是n 2> = n 2/2 + n / 2。这是真的？让我们来做一些简单的代数。

应该清楚，n2> = n（不是严格大于，因为n = 0或1的情况），假设n总是一个整数。

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

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

如果i和j都是从0到N，很容易看到O（N ^ 2）

 OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO OOOOOOOO

在这种情况下，它是：

 O OO OOO OOOO OOOOO OOOOOO OOOOOOO OOOOOOOO

这是N ^ 2的1/2，仍然是O（N ^ 2）

的确是O（n ^ 2）。在这里也可以看到一个非常相似的例子。

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

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

外循环执行N次。每次执行外循环时，内循环执行M次。结果，内循环中的语句共执行了N * M次。因此，这两个循环的总复杂度是O（N2）。

在外层循环（i = 1）的第一次迭代中，内层循环将迭代1次在外层循环（i = 2）的第二层迭代中，内层循环将迭代2层在外层循环的第三层迭代（i = 3），内部循环将迭代3次
。
。
在外循环（i = n）的FINAL迭代中，内循环将迭代n次

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

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