这个 for 循环的大 O 是什么...？

Question

第一个循环运行s O(log n) 时间但是第二个循环的运行time 取决于第一个循环的计数器，如果我们进一步检查它应该运行喜欢 (1+2+4+8+16....+N) 我只是找不到这个系列的合理答案...

for (int i = 1; i < n; i = i * 2)
{
    for (int j = 1; j < i; j++)
    {
        //const time
    }
}

Answer 1

正如你所说。如果 N 是二的幂，则 1+2+4+8+16....+N 正好是 2*N-1（几何级数之和）。这与可以简化为N的O(N)相同。

Answer 2

就像：

1 + 2 + 4 + 8 + 16 + ....+ N

= 2 ^ [O(log(N) + 1] - 1

= O(N)

What is the big-O of this for loop...?