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)。

希望这可以帮助！

Answer 2

您可以像下面这样正式地进行以获得将执行的指令的确切数量以及增长顺序：