big-o - 找出以下循环的计算复杂度

Question

For n=1 : Inner loop will execute 1 time.
For n=2 : Inner loop will execute 1+2 times.
For n=4 : Inner loop will execute 1+2+4 times.
For n=8 : Inner loop will execute 1+2+4+8 times.

...

那么我怎样才能找到计算复杂度呢？

我的回答是:内循环迭代次数 = n+(n/2)+(n/4)+(n/8)+...+(n/n)

Answer 1

总时间复杂度为 Θ(n)。要看到这一点，请注意内部循环在每次迭代中执行 Θ(i)，并且 i 取值 1, 2, 4, 8, 16, 32, ..., 2^{log n}。如果我们总结一下，使用几何级数和的公式，我们得到

1 + 2 + 4 + 8 + ... + 2^{log n} = 2^{log n + 1} - 1 = 2 · 2^{log n} - 1 = 2n - 1

所以完成的总功是 Θ(n)。

希望这对您有所帮助!