big-o - 指数和对数复杂度的大 O 表示法

Question

关于大 O 符号有很多问题，但我没有找到这个问题的明确答案。

我们这样写：
O(5n) = O(n)
和
O(3n^2 + n + 2) = O(n^2)

我们可以这样写：
O(2^(2n)) = O(2^n)？

对数复杂度也一样：O(n log(4n)) = O(n log(n))？

Answer 1

您可以删除的唯一常数是加法和乘法常数。含义 O(f( n )) = O(f( n ) + C) = O(C × f( n ))。

2 ^{2 n} = (2 ⁿ ) ²。这 2 个常数不能忽略，因为它是一个指数。正如 O( n ) 和 O( n ² ) 是不同的复杂度类别一样，O(2 ⁿ ) 和 O(2 ^{2 n} ) 也是如此。

另一方面，是的，O( n log 4 n ) = O( n log n )。我们可以使用对数恒等式将 4 转换为乘法常数： O( n log 4 n ) = O( n (log n + log 4)) = O( n log n + (log 4) n ) = O( n log n + n ) = O( n log n )。