带平方根的while循环的运行时间/时间复杂度

Question

这个问题看起来比较简单，但是我好像找不到n的运行时间。

这是问题所在：

j = n;
while(j >= 2) {
    j = j^(1/2)
}

我真的不需要总运行时间，我只需要知道如何计算第二行和第三行被击中的次数（它们应该相同）。我也想知道是否有某种公式可以找到这个。我可以看到上面的内容相当于：

for(j = n; n >= 2; j = j^(1/2)

请注意，操作的类型无关紧要，每次执行一行，都计为 1 个时间单位。所以第 1 行只是 1 个时间单位，第 2 行将是：

• 如果 n 为 1，则为 0 个时间单位，
• 如果 n 为 2，则为 1 个时间单位，
• 如果 n 为 4，则为 2 个时间单位，
• 如果 n 为 16，则为 3 个时间单位，依此类推。

在此先感谢任何提供帮助的人！这是非常赞赏！

Answer 1

向后工作以获得第 2 行的时间单位数：

                                   time
n              n       log_2(n)    units
1              1        0          0
2              2        1          1
4              4        2          2
16             16       4          3
16^2           256      8          4
(16^2)^2       65536    16         5
((16^2)^2)^2)  ...      32         6

换句话说，对于时间单位的数量t，n是 2^(2^(t-1)) 除了t = 0在这种情况下的情况n = 1。

要扭转这一点，你有

当 n < 2 时，t = 0

t = log ₂ (log ₂ (n)) + 1 当 n >= 2

其中 log ₂ (x) 称为 x 的二进制对数。