指数函数的大O符号 [英] Big O Notation Of Exponential Functions

问题描述

我注意到1000n或10n的big-O与O（n）是相同的，但是2 ^ n和3 ^ n的big-O是不同的：O（2 ^ n）和O（3 ^ n），我不明白的是为什么在这种情况下我们不能忽略常量（2或3），以及是否有任何数学证明来证明这一点呢？

I have noticed that big-O of 1000n or 10n is the same thing as O(n), but big-O of 2^n and 3^n are different: O(2^n) and O(3^n), what I don't get is why can't we ignore the constants in this case (2 or 3) and whether there is any mathematical proof justifying this?

推荐答案

因为没有 k 的常数满足不等式 3 ^ n< = k * 2 ^ n 表示任意大的 n 。因此， f（n）= 3 ^ n 不是 O（2 ^ n）的成员。

Because there is no constant value of k that satisfies the inequality 3^n <= k * 2^n for arbitrarily large n. Thus f(n) = 3^n is not a member of O(2^n).

请参见 http://en.wikipedia.org/ wiki / Big_O_notation＃Family_of_Bachmann.E2.80.93Landau_notations 。

这篇关于指数函数的大O符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！