这个while循环的时间复杂度是多少？

Question

while(n>x) 
  x*=x;

正确的答案是log(log(n)),我可以看到log(n),因为x ^ k> = n是while循环停止的时候.所以我得登录(n),我错过了什么？

PS:给出x = 2.

Answer 1

设a为x的原始值,并假设a> 1.

• 在第一个循环之后,x = a**2
• 在第二个循环之后,x = a**4
• 在第三个循环之后,x = a**8
• ...在第k个周期之后,x = a**(2**k)

x> = n表示

a**(2**k) >= n
2**k >= log(n)/log(a)
k >= log2(log(n)/log(a)) = log2(log(n))-log2(log(a))

Answer 2

编辑：(Given x = 2)

如果出现以下情况，您的答案是正确的：

while(n>x) 
  x*=2;

这意味着每次迭代达到结果的时间都会减少一半。

x但由于每次迭代都会缩短时间并且时间x不断增加，因此您将得到O log(Log(n)).

Log(n)是每次迭代跳过一半的复杂度（B 树）。