无法理解嵌套循环的大 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，依此类推。

如果您计算 i=0..log n 的 n/(2^i) 之和，您将大致得到 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                
   }
}

Can't understand big-O of a nested loop