具有平方根的while循环的运行时间/时间复杂度 [英] Running time/time complexity for while loop with square root

问题描述

这个问题看起来相对简单，但我似乎找不到n的运行时间。

This question looks relatively simple, but I can't seem to find the running time in terms of n.

这里是问题所在：

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

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

I don't really need the total running time, I just need to know how to calculate the amount of times the second and third lines are hit (they should be the same). I'd like to know if there is some sort of formula for finding this, as well. I can see that the above is the equivalent of:

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

请注意，每次行被执行，它以1个时间单位为单位，因此第1行将是1个时间单位，第2行将是：

Please note that the type of operation doesn't matter, each time a line is executed, it counts as 1 time unit. So line 1 would just be 1 time unit, line 2 would be:

• 0次如果n为1，


• 如果n为2，则为1个时间单位

如果n为4，则为2个时间单位，

• 如果n为16，则为3个时间单位，等等。

• 0 time units if n were 1,
• 1 time unit if n were 2,
• 2 time units if n were 4,
• 3 time units if n were 16, etc.

在此先感谢提供帮助的任何人！

Thanks in advance to anyone who offers help! It is very much appreciated!

推荐答案

向后工作以获取第2行的时间单位数。

Work backwards to get the number of time units for line 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 。

In other words, for the number of time units t, n is 2^(2^(t-1)) except for the case t = 0 in which case n = 1.

要扭转这种情况，当n<时，您有

To reverse this, you have

t = 0 ; 2

t = 0 when n < 2

t = log ₂ （log ₂ （n））+ 1，当n> = 2

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

其中log ₂ （x）被称为 x的二进制对数。

where log₂(x) is known as the binary logarithm of x.

这篇关于具有平方根的while循环的运行时间/时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！