我注意到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/

10-11 22:58
查看更多