运行 time/time 带平方根的 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 行是：

• 0 个时间单位如果 n 为 1，
• 如果 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.

要扭转这一局面，您需要

t = 0 当 n < 2

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

其中 log₂(x) 被称为 x 的 binary logarithm。