为什么下面的算法会有运行时log(log(n))？
Why does the following algorithm have runtime log(log(n))?
不明白算法的运行时间怎么可以log(log(n))。有人可以帮助我吗？
s=1
while s <= (log n)^2 do
s=3s
符号说明：log(n)表示整个解决方案中的log2(n)。
嗯，我想(log n)^2表示log(n)的平方，也就是log(n)*log(n)。让我们尝试分析算法。
它从 s=1 开始，像 1,3,9,27...
由于是3的指数，每次迭代后s可以表示为3^m，m是从1开始的迭代次数。
我们将进行这些迭代，直到 s 变得大于 log(n)*log(n)。所以在某些时候 3^m 将等于 log(n)*log(n)。
求解方程：
3^m = log(n) * log(n)
m = log3(log(n) * log(n))
该算法的时间复杂度可以表示为O(m)。我们必须用 n 来表达 m。
log3(log(n) * log(n)) = log3(log(n)) + log3(log(n))
= 2 * log3(log(n)) 对于 Big-Oh 表示法，常量无关紧要。所以让我们去掉 2.
时间复杂度=O(log3(log(n)))
好吧，事情是这样的：根据 Big-Oh 符号的定义，它表示我们函数的 上限 运行时。因此O(n) ⊆ O(n^2)。
请注意 log3(a) < log2(a) 在一个点之后。
按照同样的逻辑，我们可以得出结论 O(log3(log(n)) ⊆ O(log(log(n)).
所以算法的时间复杂度：O(log(logn))
不是最科学的解释，但我希望你明白了。
这是一个更普遍原则的特例。考虑以下循环：
s = 1
while s < k:
s = 3s
这个循环要循环多少次运行？那么，s 取的值将等于 1, 3, 9, 27, 81, ... = 30, 31, 32, 33, ...更一般地，在循环的第 i 次迭代中，s 的值将为 3i.
这个循环在 3i 超过 k 时立即停止 运行ning。要弄清楚它在哪里，我们可以等同并求解：
3i = k
i = log3 k
所以这个循环会运行一共log3k次。
现在，如果我们改用这个循环，您认为会发生什么？
s = 1
while s < k:
s = 4s
使用类似的逻辑，循环迭代次数将是 log4 k。更一般地说，如果我们有以下循环：
s = 1
while s < k:
s = c * s
那么假设c>1，迭代次数就是logck.
鉴于此，让我们看看您的循环：
s = 1
while s <= (log n)^2 do
s = 3s
根据上面的推理，这个循环的迭代次数为 log3 (log n)2。使用对数的性质，我们可以将其简化为
log3 (log n)2
= 2 log3 log n
= O(log log n).
不明白算法的运行时间怎么可以log(log(n))。有人可以帮助我吗？
s=1
while s <= (log n)^2 do
s=3s
符号说明：log(n)表示整个解决方案中的log2(n)。
嗯，我想(log n)^2表示log(n)的平方，也就是log(n)*log(n)。让我们尝试分析算法。
它从 s=1 开始，像 1,3,9,27...
由于是3的指数，每次迭代后s可以表示为3^m，m是从1开始的迭代次数。
我们将进行这些迭代，直到 s 变得大于 log(n)*log(n)。所以在某些时候 3^m 将等于 log(n)*log(n)。
求解方程：
3^m = log(n) * log(n)
m = log3(log(n) * log(n))
该算法的时间复杂度可以表示为O(m)。我们必须用 n 来表达 m。
log3(log(n) * log(n)) = log3(log(n)) + log3(log(n))
= 2 * log3(log(n)) 对于 Big-Oh 表示法，常量无关紧要。所以让我们去掉 2.
时间复杂度=O(log3(log(n)))
好吧，事情是这样的：根据 Big-Oh 符号的定义，它表示我们函数的 上限 运行时。因此O(n) ⊆ O(n^2)。
请注意 log3(a) < log2(a) 在一个点之后。
按照同样的逻辑，我们可以得出结论 O(log3(log(n)) ⊆ O(log(log(n)).
所以算法的时间复杂度：O(log(logn))
不是最科学的解释，但我希望你明白了。
这是一个更普遍原则的特例。考虑以下循环：
s = 1
while s < k:
s = 3s
这个循环要循环多少次运行？那么，s 取的值将等于 1, 3, 9, 27, 81, ... = 30, 31, 32, 33, ...更一般地，在循环的第 i 次迭代中，s 的值将为 3i.
这个循环在 3i 超过 k 时立即停止 运行ning。要弄清楚它在哪里，我们可以等同并求解：
3i = k
i = log3 k
所以这个循环会运行一共log3k次。
现在，如果我们改用这个循环，您认为会发生什么？
s = 1
while s < k:
s = 4s
使用类似的逻辑，循环迭代次数将是 log4 k。更一般地说，如果我们有以下循环：
s = 1
while s < k:
s = c * s
那么假设c>1，迭代次数就是logck.
鉴于此，让我们看看您的循环：
s = 1
while s <= (log n)^2 do
s = 3s
根据上面的推理，这个循环的迭代次数为 log3 (log n)2。使用对数的性质，我们可以将其简化为
log3 (log n)2
= 2 log3 log n
= O(log log n).