O(n)是否大于O(2 ^ log n) [英] Is O(n) greater than O(2^log n)

问题描述

我读了一本数据结构书的复杂性层次结构图，其中n大于2 ^{log n} .但是不知道如何以及为什么.在使用2的幂作为n的简单示例时，我得到的值等于n.

I read in a data structures book complexity hierarchy diagram that n is greater than 2^{log n}. But cannot understand how and why. On using simple examples in power of 2 as n, I get values equal to n.

书中没有提到它，但我假设它以2为基础(因为上下文是DS的复杂性)

It is not mentioned in book , but I am assuming it to base 2 ( as context is DS complexity)

a)是O(n) > O(pow(2,logn))吗?

b)O(pow(2,log n))比O(n)好吗?

推荐答案

注意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).

Notice that 2^{log_b n} = 2^{log₂ n / log₂ b} = n^{(1 / log₂ b)}. If log₂ b ≥ 1 (that is, b ≥ 2), then this entire expression is strictly less than n and is therefore O(n). If log₂ b < 1 (that is, b < 2), then this expression is of the form n^{1 + ε} and therefore not O(n). Therefore, it boils down to what the log base is. If b ≥ 2, then the expression is O(n). If b < 2, then the expression is ω(n).

希望这会有所帮助！

这篇关于O(n)是否大于O(2 ^ log n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！