什么是嵌套循环,其中在内部循环的迭代次数由外循环的当前迭代中确定的大O?
-
21-08-2019 - |
题
什么是以下的嵌套循环的大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表示法。
其他提示
是。回想一下大O的定义: O(F(N))通过定义表示,运行时间的 T(n)的≤ KF(n)的对于某一常数的ķ。在这种情况下,步骤的数目将是(N-1)+(N-2)+ ... + 0 的,其重排为0至n-1的总和;这是
T(N)=(N-1)((N-1)+1)/ 2 。
重新排列这一点,你可以看到的 T(n)的将总是≤1/2(N²);由定义,因而 T(N)= O(N²)
有n值的平方,如果你忽略的System.out.println。如果假设由所花费的时间将在其输出(其很可能不是当然)是线性的,我怀疑你结束了O((N ^ 2)*日志N)。
我提到这一点并不挑剔,只是要指出的是,你不只是需要采取明显的循环考虑制定复杂的时候 - 你需要看看你叫什么,以及复杂
是,这将是N的平方。的实际步数将1到N,其为0.5 *之和(N - 1)^ 2,如果我没有记错。大O只考虑了最高exponant和没有常数,因此,这是静像N的平方。
如果你有N = 10,则迭代将是:10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1。 (这是:十次迭代加9次迭代加八次迭代...等)。
现在,你需要寻找到(在本例中10)另外,你可以有多少次得到N:
1:(10),2:(9 + 1),3:(8 + 2),4:(7 + 3),5:(6 + 4)。这是5倍...和搁置5次迭代。
现在你知道你有五个几十+ 5:
10(5)+ 5
在F(N)(或N),我们可以很容易地看到,这将是方面:
F(N)= N(N / 2)+ N / 2 =(N ^ 2)/ 2 + N / 2 =(N ^ 2 + N)/ 2 ...这是这些完全的复杂性嵌套循环。
不过,考虑到大O的渐近行为,我们可以摆脱的F(N)少显著价值,这是一个n和分母的。
结果:为O(n ^ 2)