什么是嵌套循环的Big-O,内循环中的迭代次数是由外循环的当前迭代决定的?

什么是以下嵌套循环的Big-O时间复杂度:

for(int i = 0; i < N; i++) { for(int j = i + 1; j < N; j++) { System.out.println("i = " + i + " j = " + j); } } 

会不会是O(N ^ 2)呢?

是的,它仍然是O(n ^ 2),它有一个较小的常数因子,但是这并不影响O符号。

是。 回顾一下Big-O: O(f(n))的定义,定义为运算时间T(n) ≤kf(n)对于某个常数k 。 在这种情况下,步数将是(n-1)+(n-2)+ … + 0 ,其重新排列为0到n-1之和; 这是

T(n)=(n-1)((n-1)+1)/ 2

重新排列,你可以看到T(n)将总是≤1/ 2 (n2 ); 根据定义,因此T(n)= O(n 2)

如果忽略System.out.println,则为N平方。 如果你认为它的输出时间是线性的(当然这可能不是这样),我怀疑你会以O((N ^ 2)* logN)结束。

我提到这并不挑剔,但是要指出,在处理复杂性时,不仅需要考虑明显的循环,还需要考虑所谓的复杂性。

是的,这将是N平方。 如果我没有弄错的话,实际的步数将是1到N之和,即.5 *(N-1)^ 2。 大O只考虑最高的无常数,因此,这仍然是N平方。

如果你有N = 10,你的迭代将是:10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1。 (这是:十次迭代加九次迭代加八次迭代…等)。

现在,你需要find多less次你可以得到一个N(在这个例子中是10):

1:(10),2:(9 + 1),3:(8 + 2),4:(7 + 3),5:(6 + 4) 这是5次…并rest5次迭代。

现在你知道你有五十+5:

10(5)+5

就f(n)(或N)而言,我们可以很容易地看到这将是:

f(n)= n(n / 2)+ n / 2 =(n ^ 2)/ 2 + n / 2 =(n ^ 2 + n)/ 2 …这正是这些嵌套循环的复杂性。

但是,考虑到大O的渐近行为,我们可以去掉单个n和分母f(n)的重要值。

结果:O(n ^ 2)

从内部循环到外部循环开始的AFAIL是计算嵌套循环复杂度的充分方法。 在这里输入图像描述