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

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 次乘法。我想你可以从这里拿走它:)