指数和对数复杂度的大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).