What is the Big-O time complexity of the following nested loops:
以下嵌套循环的Big-O时间复杂度是多少:
for(int i = 0; i < N; i++) { for(int j = i + 1; j < N; j++) { System.out.println("i = " + i + " j = " + j); }}Would it be O(N^2) still?
它还是O(N ^ 2)吗?
6 个解决方案
#1
Yep, it's still O(n^2), it has a smaller constant factor, but that doesn't affect O notation.
是的,它仍然是O(n ^ 2),它具有较小的常数因子,但这不会影响O表示法。
#2
Yes. Recall the definition of Big-O: O(f(n)) by definition says that the run time T(n) ≤ kf(n) for some constant k. In this case, the number of steps will be (n-1)+(n-2)+...+0, which rearranges to the sum of 0 to n-1; this is
是。回想一下Big-O的定义:O(f(n))按定义说某些常数k的运行时间T(n)≤kf(n)。在这种情况下,步数将是(n-1)+(n-2)+ ... + 0,其重新排列为0到n-1的和;这是
T(n)=(n-1)((n-1)+1)/2.
Rearrange that and you can see that T(n) will always be ≤ 1/2(n²); by the definition, thus T(n) = O(n²).
重新排列,你可以看到T(n)总是≤1/ 2(n²);根据定义,因此T(n)= O(n 2)。
#3
It's N squared if you ignore the System.out.println. If you assume that the time taken by that will be linear in its output (which it may well not be, of course), I suspect you end up with O ( (N^2) * log N).
如果忽略System.out.println,则为N平方。如果你假设它所花费的时间在它的输出中是线性的(当然它可能不是),我怀疑你最终得到O((N ^ 2)* log N)。
I mention this not to be picky, but just to point out that you don't just need to take the obvious loops into account when working out complexity - you need to look at the complexity of what you call as well.
我提到这一点并不挑剔,但只是要指出在制定复杂性时你不仅需要考虑明显的循环 - 你需要考虑你所谓的复杂性。
#4
Yes, it would be N squared. The actual number of steps would the sum of 1 to N, which is .5*(N - 1)^2, if I'm not mistaken. Big O only takes into account the highest exponant and no constants, and thus, this is still N squared.
是的,它将是N平方。如果我没有弄错的话,实际的步数是1到N的总和,即.5 *(N - 1)^ 2。 Big O只考虑最高的指数和没有常数,因此,这仍然是N平方。
#5
If you had N = 10, you iterations would be: 10+9+8+7+6+5+4+3+2+1. (this is: ten iterations plus nine iterations plus eight iterations... etc.).
如果您有N = 10,则迭代次数为:10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1。 (这是:十次迭代加上九次迭代加上八次迭代......等等)。
Now, you need to find into the addition how many times you can get a N (10 in the example):
现在,您需要找到添加N次的次数(示例中为10):
1:(10), 2:(9+1), 3:(8+2), 4:(7+3), 5:(6+4). Which is 5 times... and rests 5 iterations.
1:(10),2:(9 + 1),3:(8 + 2),4:(7 + 3),5:(6 + 4)。这是5次......并且休息5次。
Now you know that you have five tens + 5:
现在你知道你有五十个+5:
10(5) + 5
10(5)+ 5
In terms of f(n) (or N), we can easily see that this would be:
就f(n)(或N)而言,我们可以很容易地看出这将是:
f(n) = n(n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2... this is exactly the complexity of these nested loop.
f(n)= n(n / 2)+ n / 2 =(n ^ 2)/ 2 + n / 2 =(n ^ 2 + n)/ 2 ......这正是这些嵌套循环的复杂性。
But, considering the asymptotic behavior of Big O, we can get rid of the less significant values of f(n), which are the single n and the denominator.
但是,考虑到Big O的渐近行为,我们可以摆脱f(n)的不太重要的值,即单个n和分母。
Result: O(n^2)
#6
AFAIL, being begun from inner loop through outer ones is adequate way for calculation of nested loop complexity.
AFAIL,从内部循环开始到外部循环,是计算嵌套循环复杂性的适当方法。
#1
Yep, it's still O(n^2), it has a smaller constant factor, but that doesn't affect O notation.
是的,它仍然是O(n ^ 2),它具有较小的常数因子,但这不会影响O表示法。
#2
Yes. Recall the definition of Big-O: O(f(n)) by definition says that the run time T(n) ≤ kf(n) for some constant k. In this case, the number of steps will be (n-1)+(n-2)+...+0, which rearranges to the sum of 0 to n-1; this is
是。回想一下Big-O的定义:O(f(n))按定义说某些常数k的运行时间T(n)≤kf(n)。在这种情况下,步数将是(n-1)+(n-2)+ ... + 0,其重新排列为0到n-1的和;这是
T(n)=(n-1)((n-1)+1)/2.
Rearrange that and you can see that T(n) will always be ≤ 1/2(n²); by the definition, thus T(n) = O(n²).
重新排列,你可以看到T(n)总是≤1/ 2(n²);根据定义,因此T(n)= O(n 2)。
#3
It's N squared if you ignore the System.out.println. If you assume that the time taken by that will be linear in its output (which it may well not be, of course), I suspect you end up with O ( (N^2) * log N).
如果忽略System.out.println,则为N平方。如果你假设它所花费的时间在它的输出中是线性的(当然它可能不是),我怀疑你最终得到O((N ^ 2)* log N)。
I mention this not to be picky, but just to point out that you don't just need to take the obvious loops into account when working out complexity - you need to look at the complexity of what you call as well.
我提到这一点并不挑剔,但只是要指出在制定复杂性时你不仅需要考虑明显的循环 - 你需要考虑你所谓的复杂性。
#4
Yes, it would be N squared. The actual number of steps would the sum of 1 to N, which is .5*(N - 1)^2, if I'm not mistaken. Big O only takes into account the highest exponant and no constants, and thus, this is still N squared.
是的,它将是N平方。如果我没有弄错的话,实际的步数是1到N的总和,即.5 *(N - 1)^ 2。 Big O只考虑最高的指数和没有常数,因此,这仍然是N平方。
#5
If you had N = 10, you iterations would be: 10+9+8+7+6+5+4+3+2+1. (this is: ten iterations plus nine iterations plus eight iterations... etc.).
如果您有N = 10,则迭代次数为:10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1。 (这是:十次迭代加上九次迭代加上八次迭代......等等)。
Now, you need to find into the addition how many times you can get a N (10 in the example):
现在,您需要找到添加N次的次数(示例中为10):
1:(10), 2:(9+1), 3:(8+2), 4:(7+3), 5:(6+4). Which is 5 times... and rests 5 iterations.
1:(10),2:(9 + 1),3:(8 + 2),4:(7 + 3),5:(6 + 4)。这是5次......并且休息5次。
Now you know that you have five tens + 5:
现在你知道你有五十个+5:
10(5) + 5
10(5)+ 5
In terms of f(n) (or N), we can easily see that this would be:
就f(n)(或N)而言,我们可以很容易地看出这将是:
f(n) = n(n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2... this is exactly the complexity of these nested loop.
f(n)= n(n / 2)+ n / 2 =(n ^ 2)/ 2 + n / 2 =(n ^ 2 + n)/ 2 ......这正是这些嵌套循环的复杂性。
But, considering the asymptotic behavior of Big O, we can get rid of the less significant values of f(n), which are the single n and the denominator.
但是,考虑到Big O的渐近行为,我们可以摆脱f(n)的不太重要的值,即单个n和分母。
Result: O(n^2)
#6
AFAIL, being begun from inner loop through outer ones is adequate way for calculation of nested loop complexity.
AFAIL,从内部循环开始到外部循环,是计算嵌套循环复杂性的适当方法。