algorithm - 无法理解嵌套循环的大 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 意味着一种算法，其中内循环绑定(bind)到 i 而不是 n。

这个答案涉及以下算法:

for (int i = n ; i >= 1; i = i/2) {
   for ( int j = 1; j <= i ; j++) {
     //do something                
   }
}