这里有 2 个循环，第一个循环以指数步长从 1 到 n（不包括）。

这个循环执行 floor(log(2,n - 1)) = p 次。并且对于每次迭代 i = 2^k，其中 k = 0..p 包括在内。第二个循环对每个 i 执行 i 次，所以我们需要做的只是对 2^k 求和 k = 0..p。这是乘数为 2 的几何级数。

Sum = 2^0*(2^(p-1)-1)/(2-1) = 2^(p-1)-1 = 2^(floor(log(2,n-1)))-1

由于a^(log(a,b)) = b，我们可以说Sum = O(n)

附言关于这个形状。我想，这个形状代表了几何级数，并显示了我们为每个 i 执行的迭代次数。此形状的正方形是执行的操作总数。

这是使用 big-O 格言的好地方

如有疑问，请彻底解决！

也就是说，从嵌套最深的循环开始，计算其复杂性，然后重复直到计算出运行时。

这里，你有这个代码：

for(int i = 1; i < n; i = i * 2)
    for(int j = 0; j < i; j++)
       //*** O(1)_operations;

那么让我们从内部循环开始。该循环运行 i 次，每次迭代执行 O(1) 工作，因此它总共执行 O(i) 工作。让我们用类似的东西替换循环：

for (int i = 1; i < n; i = i * 2) {
    // do O(i) work
}

现在的问题是如何计算出这个循环的作用。请注意，i 取值 1、2、4、8、……，直到达到或超过 n。在最坏的情况下，这意味着 i 的最大值将在 2n 左右（你明白为什么吗？）。我们也在每次迭代中做 O(i) 的工作，所以这里完成的工作将（大致）

1 + 2 + 4 + 8 + 16 + 32 + … + 2n。

我们现在需要做的就是弄清楚这到底是什么。有几种方法可以做到这一点。其中之一是使用与您链接的图片类似的图片。你有没有注意到它是如何将一堆 2 的幂相加，以及整个矩形的面积如何大致等于下一个 2 的幂？事实上，确切的数学答案是

1 + 2 + 4 + 8 + … + 2^k = 2^k+1 - 1.

你能看出图片中这是从哪里来的吗？

在我们的例子中，我们有

1 + 2 + 4 + 8 + ... + 2n = 4n - 1,

所以这里完成的总工作是 O(n)。