我在一本数据结构书的复杂度层次图中读到 n 大于 2log n。但无法理解如何以及为什么。在使用 2 的幂作为 n 的简单示例时，我得到的值等于 n。
书中没有提到它，但我假设它以 2 为基数(因为上下文是 DS 复杂性)
a) Is
O(n) > O(pow(2,logn))?b) Is
O(pow(2,log n))better thanO(n)?
最佳答案
请注意，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)。
希望这可以帮助!
关于math - O(n) 是否大于 O(2^log n)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27387198/