big-o - 此算法中的加法和乘法运算符的数量

Question

考虑以下算法：

i := 1
t := 0
    while i ≤ n
       t := t + i
       i := 2i

我有兴趣找出这个算法执行了多少加法和乘法运算；但是，我遇到了麻烦。我知道每次迭代后 i 的值加倍，但我不知道如何推广算法以给出正确数量的操作，直到 n 的值。如果有人能对这个问题有所了解，我将不胜感激。

谢谢！

Answer 1

由于每个循环的值i加倍并且i <= n

i*2^x <= n

最大化 x 给出循环数。因为 i = 1

2^x = n
x = floor log(n)

我们每个循环执行 1 次加法和 1 次乘法。我想你可以从这里拿走:)