当索引每次迭代平方时,while循环的大O表示法

Question

我需要帮助理解这个算法的时间复杂度以及以这种方式迭代的任何算法(i = i*i),我无法弄清楚这个循环与n成比例地执行多少次:它是log n吗？log log n？或类似的东西？我该如何分析这样的事情？提前致谢

function(n):
    i=5
    while i<n: 
    {
       do.something()
       i = i*i
    }

Answer 1

首先观察在循环的k次重复之后,i可以将值计算为5 ^{2 k}.

环路将要停止时的值i达到n,因此需要重写公式n = 5 ^{2 ķ}对于k:日志₅ n = 2的^ķ,登录₂(对数₅ N)= K

因此,循环的复杂性是O(log ₂(log ₅ n))