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

Question

我在一本数据结构书的复杂度层次图中读到 n 大于 2log n。但无法理解如何以及为什么。在使用 2 的幂作为 n 的简单示例时，我得到的值等于 n。
书中没有提到它，但我假设它以 2 为基数(因为上下文是 DS 复杂性)

a) Is O(n) > O(pow(2,logn))?

b) Is O(pow(2,log n)) better than O(n)?

Answer 1

请注意，2logb n = 2log2 n/log2 b = n(1/log2 b)。如果 log2 b ≥ 1(即 b ≥ 2)，则整个表达式严格小于 n，因此为 O(n)。如果 log2 b < 1(即 b < 2)，则该表达式的形式为 n1 + ε，因此不是 O(n)。因此，它归结为日志基数。如果 b ≥ 2，则表达式为 O(n)。如果 b < 2，则表达式为 ω(n)。

希望这可以帮助!