无法理解嵌套循环的大O.

Question

我在解决以下关于分析以下两种算法的问题的答案时遇到了问题.

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)吗？

Answer 1

第一次迭代将执行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                
   }
}