指数函数的大O符号

我注意到1000n或10n的大O与O（n）是相同的，但是2^n和3^n的大O是不同的：O（2^n ）和O（3^n），我没有得到的是为什么我们不能忽略这种情况下的常量（2或3）以及是否有任何数学证明证明这一点？指数函数的大O符号

来源

2013-09-29 fYre

您不会忽略大O符号中的常量。你忽略系数。 2和3是基础，而不是系数。 – kqr

你能说出Big-Oh的定义吗？记住Big-Oh有一个数学定义，不应该直接使用。记住“有时你可以忽略常量”是一种坏习惯，在我看来。 – rliu

因为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。

来源

2013-09-29 18:30:23

准确地说，您正在展示一个声称“O（3^n）= O（2^n）”的反例。特别是，'f（n）= 3^n'在'O（3^n）'中，但不在'O（2^n）'中，使用上面给出的参数。因此，这些集合不等于通过扩张性公理 – rliu

@roliu：我不知道这个公理是什么，但是，这是暗示的论证;） –

这是最流行的集合论中的一个公理，ZFC：https：/ /en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory。它只是说“如果它们包含相同的元素，则两组相等”。从来没有人以真实的证据引用它，但我只是试图说服SO开始使用实际的数学推理而不是直觉（对于数学术语来说，这是非常冗长的）。如果您只是想在编写代码时决定使用哪个实现，则可以使用直觉。当有人说“证明这一点”时，我认为你应该，你知道，使用数学:) – rliu

虽然对于原来的提问者来说这可能不再有用，
我认为可以以更简单的方式接近它。

O形表示法的基本defenition：当且仅当F（G）将是O（G（N）），
则存在一个有理数C，对于其保持使f（G）= C * G（N），对于n> = N0
（N0为一个数字，你要振作精神）

让我们尝试应用此3为O^N（2^n）的
3^N = 2^n * c
3^n = 2^n *（3^n/2^n）
3^N = 2^N *（3/2）^ n的
3^N = 2^N * 1.5^N

这意味着C = 1.5^n的是不是一个合理的数字，但它本身就是一个指数函数。

在另一方面，以下为O 3^N（2^n）的相同，我们将得到2^N < = 3^N *（2/3）^ n的

这可能看起来像是一个冲突，直到你意识到所有n> 0的0.75^n < 1，这意味着如果你采取任何c> 1，它将大于0。从n = 0开始的67^n

来源

2014-10-17 11:56:05

为了应对两个复杂性f（n）和g（n）你应用的极限： lim_ {n - > \ inf} f（n）/ g（n）和你有三个可能的答案：

1）lim_ {n - > \ inf} f（n）/ g（n）= 0;这意味着f（n）∈O（g（n））和g（n）∉O（f（n））

2）lim_ {n-> \ inf} f（n）/ g n）= +/- inf;这意味着f（n）∉O（g（n））和g（n）∈O（f（n））

3）lim_ {n-> \ inf} f（n）/ g n）∈实数;这意味着f（n）∈O（g（n））和g（n）∈O（f（n））

然后去demostrade 2^n∈O（3^n）

lim_ {N - > \ INF} 2^N/3^N = lim_ {N - > \ INF}（2/3）^ n = 0的

和IS实例阐述，并且我们也demostraded 3 （2^n），并且很容易看出，这使得极限收敛到0，那么极限的结果取决于常数，我的意思是lim_ {n-> inf} a^n = 0如果0 < a < 1并且lim_ {n-inf} a^n = inf如果a> 1;

为了更好地理解检查：算法导论，第三版通过托马斯·H·科门，查尔斯·E·莱泽森，罗纳德L.维斯特和克利福德·斯坦

我的算法教授，我希望它帮助您。保重。

来源

2017-02-08 17:31:31

指数函数的大O符号

回答

相关问题