我在理解以下有关分析以下两种算法的问题的答案时遇到问题。
for (int i = n ; i >= 1; i = i/2) {
for ( int j = 1; j <= n ; j++) {
//do something
}
}
根据答案，上述算法的复杂度为O（n）。它不应该更低吗，因为外循环总是将我们必须经过的量减半。我认为应该是O（n / 2 *）的意思吗？
for ( int j = 1; j <= n ; j++ ) {
for ( int i = n ; i >= j ; i = i / 2 ) {
//do something
}
}
如果我是正确的，那么这个就是O（n log n）？
第一次迭代将执行n步骤，第二次将执行n/2，第三次将执行n/4，依此类推。
如果计算的总和n/(2^i)为i=0..log n您将得到大约2n，这就是为什么它是O(n)。
如果您n将总和取出，仅对1/(2^i)部分求和，则将得到2。看一个例子：
1 + 1/2 + 1/4 + 1/8 + 1/16 + ... = 1 + 0.5 + 0.25 + 0.125 + 0.0625 + ... = 2
每个下一个元素小两倍，因此总和永远不会超过2。
您对第二个嵌套循环示例是正确的-它是O(n log n)。
编辑：
在ringø发表评论后，我重新阅读了问题，实际上算法与我所理解的不同。ringø是正确的，问题中描述的算法是O(n log n)。但是，从上下文的角度来看，我认为OP意味着一种将内部循环绑定在一起i而不是的算法n。
该答案与以下算法有关：
for (int i = n ; i >= 1; i = i/2) {
for ( int j = 1; j <= i ; j++) {
//do something
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句