algorithm - 在证明Big O、Big Omega和Big Theta时，我们如何识别C和n0？

Question

正如问题所说，我们如何准确地找到给定界限的 c 和 n0？

例如，当我不得不解决这个问题时......证明 5n^2+2n+1 = O(n^2)

我能够查看 2n 并说“这永远不会大于 2n^2”，对于 1 我也能够说“这永远不会大于 n^2”。考虑到这一点，我能够选择 C ​​= 8 和 n0 = 1。

但是，当我遇到诸如...使用大 O 表示法的基本定义证明 n^3=O(2^n)。

我完全不知道该怎么做，因为我唯一需要处理的是 n^3。我如何为这些类型的问题识别 C 和 n0？

Answer 1

你需要在每个具体案例中找到一个论据，没有找到证明的算法。

在您的示例中，我们可以使用 n^3 在 o(2^n) 中是偶数，这清楚地暗示它在 O(2^n) 中。要查看前者，请考虑 n->infinity of (n^3/2^n) 的极限。使用L'Hôpital's rule三次，您会看到限制为 0。