math - 证明语句的大 O

Question

我很难证明这n^k适用O(2^n)于所有人k。我试过lg2两边都吃k*lgn=n，但这是错误的。我不确定我还能如何证明这一点。

Answer 1

为了证明 n ^k是 O(2 ⁿ )，请注意

n ^k = (2 ^{lg n} ) ^k = 2 ^{k lg n}

所以现在你想找到一个 n ₀和 c 使得对于所有 n ≥ n ₀，

2^{千 lg n} ≤ c 2 ⁿ

现在，让 c = 1，然后考虑当 n = 2 ^m对于某些 m 时会发生什么。如果我们这样做，我们会得到

2 ^{k lg n} ≤ c 2 ⁿ = 2 ⁿ

2 ^{k lg 2 m} ≤ 2 ^{2 m}

2^公里≤2 ^2米

并且，由于 2 ⁿ是一个单调递增的函数，这等价于

公里≤2^米

现在，让我们把事情结束吧。假设我们让 m = max{k, 4}，所以 k ≤ m。因此我们有

公里≤米²

我们也有

米^2≤2米_

因为对于任何 m ≥ 4，m ² ≤ 2 ^m，并且我们通过选择 m 来确保 m = max{k, 4}。结合这个，我们得到那个

公里≤2^米

这相当于我们想要在上面展示的内容。因此，如果我们选择任何 n ≥ 2 ^m = 2 ^{max{4, k}}，那么 n ^k ≤ 2 ⁿ将是真的。因此，通过大 O 符号的正式定义，我们得到 n ^k = O(2 ⁿ )。

我认为这个数学是正确的；如果我错了，请告诉我！

希望这可以帮助！

Answer 2

我还不能发表评论，所以我会回答这个问题。

而不是像你一直试图做的那样减少等式，你应该尝试找到一个满足这里找到的大 O 表示法的正式定义的一个n0和一个： http ://en.wikipedia.org/wiki/Big_O_notation#Formal_definitionM

可能有用的东西n0=M=k（我还没有写出来，所以也许这不起作用，这只是为了给你一个想法）