2^ O(log log n) = O(log n)吗？

Question

2 ^ O(log log n) = O(log n)是吗？你能解释一下如何测试这种关系吗？

我尝试用C1 log(log n)代替O(log(log ))，用C2 log n代替log n来找出它们之间的关系。当我绘制函数的图时，它似乎是正确的，但我一度陷入了数学证明，不知道如何继续下去。

Answer 1

你在方向上。您可以将O(log(log n))替换为c log(log n)，并确保存在一个常量c即2 ^ O(log(log n)) < 2 ^ (c log(log n))。因此，我们将有S = 2^ (c log(log n)) = (2^(log(log n)))^c = log(n)^c。然而，您不能 say S = O(log n)。因为c可以是任意一个常量，所以你可以说S = O(n^epsilon)，epsilon可以是一个接近于零的小常数。