O(n) 是否大于 O(2^log n)

Question

我在数据结构书籍复杂性层次图中读到 n 大于 2 ^{log n}。但无法理解如何以及为什么。在使用 2 的幂作为 n 的简单示例时，我得到等于 n 的值。

书中没有提到，但我假设它以 2 为基数（因为上下文是 DS 复杂性）

a) 是O(n) > O(pow(2,logn))？

b)O(pow(2,log n))优于O(n)？

Answer 1

请注意，2 ^{log _b n} = 2 ^{log ₂ n / log ₂ b} = n ^{(1 / log ₂ b)}。如果 log ₂ b ≥ 1（即 b ≥ 2），则整个表达式严格小于 n，因此为 O(n)。如果 log ₂ b < 1（即 b < 2），则该表达式的形式为 n ^{1 + ε}，因此不是 O(n)。因此，它归结为对数基数是什么。如果 b ≥ 2，则表达式为 O(n)。如果 b < 2，则表达式为 ω(n)。

希望这可以帮助！