我注意到1000N或10N的Big-O和O(N)是一样的,但是2^N和3^N的Big-O是不同的:O(2^N)和O(3^N),我没有得到的是为什么我们不能忽略这里的常数(2或3),以及是否有任何数学证明可以证明这一点?
最佳答案
因为对于任意大的k
,没有满足不等式3^n <= k * 2^n
的常数值n
。因此f(n) = 3^n
不是O(2^n)
的成员。
见http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations。
关于algorithm - 指数函数的大O符号,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/19081673/