嵌套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。 这是真的? 让我们来做一些简单的代数。

    • 两边乘以2得到:2n²> =n²+ n?
    • 展开2n²得到:n²+n²> =n²+ n?
    • 从两边减n 2得到:n 2> = n?

    应该清楚,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