Does 2 ^ O(log log n) = O(log n)?

Question

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

我尝试用C1 log(log n)替换O(log(log n((，用C2 log n替换log n，以找到它们之间的关系。当我绘制函数时，似乎该语句是正确的，但我一度陷入数学证明，不确定如何进行。

Answer 1

No.假设一个以 2 为基数的日志，则

2^个日志N = 日志 N，

但 2^{10 对数对数}N 也在 2^{O(对数对数 N(}中，并且

2^{10 对数日志}N = (2 对数日志 N(10 = (^{日志 N}(¹⁰

。这显然不在 O(log N( 中

Answer 2

你正朝着正确的方向前进。您可以将O(log(log n))替换为c log(log n)，并确保存在2 ^ O(log(log n)) < 2 ^ (c log(log n))的常量c。因此，我们将有S = 2^ (c log(log n)) = (2^(log(log n)))^c = log(n)^c.但是，你不能说S = O(log n).由于c可以是任何常数，因此您可以说S = O(n^epsilon)epsilon可以是接近零的小常数。