algorithm - 这个算法的大(O)

Question

这个算法的大(O)是什么。我知道它类似于 O(log(n)) 但不是每次都减半，而是呈指数级缩小。

sum = 0
i = n
j = 2 
while(i>=1) 
    sum = sum+i 
    i = i/j
    j = 2*j

Answer 1

分母d是

d := 2^(k * (k + 1) / 2)

在循环的第 k 次迭代中。因此，当 d 大于 n 时，您必须解决导致分数小于 1

的问题

2^(k * (k + 1) / 2) > n

对于 k 和固定的 n。插入

solve 2^(k * (k + 1) / 2) > n for k

在 WolframAlpha 中给出

因此，当您从公式中删除不相关的常量时，您的算法的运行时间为 O(sqrt(log n))。