artificial-intelligence - 证明 f(n) 是 O(2^n)

Question

我了解如何使用 Big-O 的定义来证明 f(n) 是 O(n) 或 O(n^2) 但我迷失了 O(2^n) 你能帮忙证明 2^n +n ^3 + 30 是 O(2^n) 吗？Bsc AI Yr1 喜欢这一切，但复杂性让我大吃一惊！

Answer 1

Big O Notation定义了函数在接近某个值时的行为。通常，我们说无穷大，但通常“任意大的数”就足够了。

因此，您处于数学极限的世界中；Math SE在这里会有所帮助，但让我们考虑一下您的情况。为了表明：

O(2^n +n^3 + 30) == O(2^n)

我们需要证明，当n趋向于一个大数时，2^n +n^3 + 30趋向于2^n。通过检查，您可以看到，当n是 10 时，n^3是 1000，所以已经比 30 大得多（并且随着增长而n增长）。此时，2^n是 1024，所以它的数量级与 相同n^3，但也越来越大。一次n是 100，n^3是 100 万，2^n是这个数字的 5 倍（1 x 10^30）......很明显，第一项超过了其他项，n而不是我们所说的“任意大”

所以，通过检查，我们知道

O(2^n +n^3 + 30) == O(2^n)

Answer 2

好吧，这取决于您可以使用的工具。乍一看，这很明显，因此您可能必须更深入地研究证明。

基本上，与 2^n 相比，n^3 小得离谱，所以 n^3 ~ o(2^n)。

常数 30 相同。

所以

2^n + n^3 + 30 ~ 2^n + o(2^n) ~ O(2^n)根据定义。

如果不足以作为证明，你可以证明

limit n^3/2^n (when n-> infinity) = 0

Answer 3

证明n^3 < 2^n for some n > n0（通过归纳或查看一些典型的数学练习并参考它。您不必找到最小的 n0，只要找到任何 n0）

然后用这个结果证明|2^n + n^3 + 30| <= |2^n +2^n + 2^n|并在 2 和 4 之间找到一个漂亮的 c 以表明最后一项小于c*|2^n|。

毕竟，把所有东西写在一起，你应该有类似的东西|2^n +n^3 + 30| <= ... <= c*|2^n| for n > <n0> and c=<value>（完成<n0>后<value>应该是一些数字）。这是定义。

Answer 4

我不会为你解决问题，因为这听起来像是家庭作业。但我会解决一个你已经知道如何解决的问题，然后尝试让你相信这个问题没有什么不同。

所以。回想一下，当我们试图证明某个函数（称为 f(n)）属于某个其他函数（称为 g(n)）的 Big-Oh 时，我们正在做什么。我们试图证明直到某个常数因子并且随着 n 变大，f(n) 永远不会比 g(n) 差。我们通过选择两个数字 c 和 n ₀来做到这一点。第一个，c，是我之前提到的那个“常数因子”。我们将 f(n) 与 g(n) 关联如下：

f(n) ≤ cg(n) 对于所有 n ≥ n ₀

问题是，c 和 n0 不是唯一的。通常，您几乎可以任意选择一个，然后用简单的代数计算出另一个的值。所以让我们试试这个

f(n) = n² + 5n + 10

g(n) = n²

首先，我们根据常数因子 c 建立关系：

n² + 5n + 10 ≤ c n²

现在我们想自己得到 c，与 n 的一些其他函数相关，所以只需将 n² 从两边分开：

1 + 5/n + 10/n² ≤ c

我们想知道 n 的什么值（我们称之为 n ₀）对于所有较大的 n 值都是如此。好吧，我们可以选择 ac 并求解 n，或者选择 n ₀并求解 c。没关系，但让我们选择 n ₀ = 1，只要在我们看到 n 的任何地方插入它，看看会发生什么：

1 + 5/1 + 10/1 = 1 + 5 + 10 = 16 ≤ c

这就是我们的答案：如果我们选择 c 作为 16，那么只要 n 大于 1（即 n ₀ = 1），那么 f(n) 将小于 g(n)。

现在，你能用你试图解决的问题做到这一点吗？嗯……为什么不呢？我们有两个函数，f(n) 和 g(n)。我们试图证明与您知道如何解决的问题完全相同的关系。改变的只是函数的类型，从 n 中的多项式到 n 中的指数（以及混合的）。但这有关系吗？好吧，代数看起来会有点不同，但那又如何呢？是代数。