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

Question

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

我已经尝试用 O(log(log n)) 替换 O(log(log n))C1 log(log n)来找到它们之间log n的C2 log n关系。当我绘制函数图时，似乎该陈述是正确的，但我一度陷入数学证明中，不知道如何继续。

标签： algorithmtime-complexitycomplexity-theory

Answer 1

你在方向。您可以替换O(log(log n))为c log(log n)并确保存在一个常量cthat 2 ^ O(log(log n)) < 2 ^ (c log(log n))。因此，我们将拥有S = 2^ (c log(log n)) = (2^(log(log n)))^c = log(n)^c. 但是，你不能说S = O(log n)。就像c任何常数一样，你可以说它S = O(n^epsilon)可能epsilon是一个接近于零的小常数。