performance - 带平方根的 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除了t的情况外都是2^(2^(t-1)) = 0 在这种情况下 n = 1。

要扭转这一点，你有

当 n < 2 时 t = 0

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

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