algorithm - 此算法的Big(O)

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

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

最佳答案

分母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

在沃尔夫拉马尔法

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

关于algorithm - 此算法的Big(O)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48415590/