在每次迭代中i = srqt（i）时运行时间/时间复杂度[重复]

Question

这个问题在这里已有答案：

• Running time/time complexity for while loop with square root 1回答

i=n 
while i>1 :
    i = int(math.sqrt(i))
    print('*')

为什么代码的时间复杂度高于log（log（n））？ （假设sqrt（）在O（1）中运行。）

Answer 1

假设n可以用k位编码。

在第一次迭代之后，i =√n并且i可以在k / 2比特上编码。

因此，编码i所需的比特数在每一步除以2，步数为log（k）。

如k = log（n），如果我们假设sqrt复杂度为1，则复杂度为log（log（n））。