双循环的复杂性

我想弄清楚使用大O表示法for循环的复杂性。我之前在其他课上做过这个，但是这个比其他课更加严格，因为它是基于实际的算法。代码如下：双循环的复杂性

for(cnt = 0, i=1; i<=n; i++) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
}

和

for(cnt = 0, i=1; i<=n; i*=2) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
}

我已经到达第一环是O（n）的复杂性，因为它会通过列表n次。至于第二圈，我有点失落。我相信对于每个被测试的n，它都会经历循环。我（错误地）认为这意味着每次评估时循环都是O（n * i）。在我的假设中有什么是我错过的。我知道cnt ++是恒定的时间。

谢谢你在分析中的帮助。每个循环都在自己的空间中，它们不在一起。

来源

2012-09-11 Michael Guantonio

第一个样本不在O（n）中，您是否尝试在循环后使用不同的n值打印cnt？ – Kwariz

@Kwariz我道歉。我的意思是第一个例子中第一个最外层的循环是O（n）。在第一个例子中，不是整个double for循环的集合。 –

第一个示例的外部循环执行n次。对于外部循环的每次迭代，内部循环执行的次数为i，所以整体复杂度可以计算如下：第一次迭代一次加二次第二次迭代加三次第三次迭代等等，加上n第n次迭代。

1+2+3+4+5+...+n = (n*(n-1))/2 --> O(n^2)

第二个例子是棘手：因为每次迭代i双打中，外环仅执行Log2(n)倍。假设n是2功率，总的内部循环是

1+2+4+8+16+...+n

是2^Log2(n)-1 = n-1为复杂O(n)。

对于n S中的不二的幂迭代的确切数目为(2^(Log2(n)+1))-1，这仍然是O(n)：

1  -> 1 
2..3 -> 3 
4..7 -> 7 
8..15 -> 15 
16..31 -> 31 
32..63 -> 63

等。

来源

2012-09-11 18:39:18 dasblinkenlight

尽管如何将第二个示例中的两个循环组合起来？它是一个增加的复杂性，因此它总体上是O（n），还是一起乘以给出O（n log n）还是其他的东西？ –

@JBKing计算第二对循环的big-O会更容易，因为在这种情况下，我们可以使用[众所周知的几何级数前N个元素的总和]（http ：//en.wikipedia.org/wiki/Geometric_progression），它是'a *（1-r ^（N + 1））/（1-r）'。在我们的例子中，'a = 1'和'r = 2'，所以结果是'（1-2 ^（n + 1））/（1-2）'或者'2 ^（n + 1） 1'。 – dasblinkenlight

但愿这不是功课，但我不知道你至少做此尝试，所以这是我拿到这个：

cnt递增N *（N + 1）/ 2次，这使两个循环的整个集合为O（n^2）。第二个循环平均为O（n/2），即O（n）。

来源

2012-09-11 18:37:31

对于第二个样本，增量不是+2，但是我增加了一倍...这种味道不应该像日志一样复杂吗？ – Kwariz

第一个例子是O（N^2），并且What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?将是答案的问题，其中关键是要注意内循环的循环数取决于n。

第二个例子是有可能为O（n log n）的自外部循环递增在不同的规模比线性的。查看二分查找对数复杂情况的例子。在第二个例子中，外部循环是O（log n），内部循环是O（n），它们相结合产生O（n log n）复杂度。

来源

2012-09-11 18:40:12

第二个循环是'O（n）'，因为内循环上升到'i'，而不是'n'，并且'i'通过'2'的幂直到'Log2（n）'。 – dasblinkenlight

双循环的复杂性

回答

相关问题