现在，让 c = 1，然后考虑对于某些 m，当 n = 2m 时会发生什么。如果我们这样做，我们会得到
2k lg n ≤ c 2n = 2n
2k lg 2米 ≤ 22米
2公里 ≤ 22米
并且，由于 2n 是单调递增函数，因此这相当于
公里≤2米
现在，让我们完成任务吧。假设我们让 m = max{k, 4}，因此 k ≤ m。因此我们有
公里≤米2
我们也有
米2 ≤ 2米
因为对于任何 m ≥ 4，m2 ≤ 2m，并且我们有通过我们对 m 的选择确保 m = max{k, 4}。结合这个，我们得到
公里≤2米
这相当于我们上面想要显示的内容。因此，如果我们选择任何 n ≥ 2m = 2max{4, k}，则 nk ≤ 2< sup>n。因此，根据大 O 表示法的正式定义，我们得到 nk = O(2n)。
我认为这个数学是正确的；如果我错了，请告诉我！
希望这有帮助！
To show that nk is O(2n), note that
nk = (2lg n)k = 2k lg n
So now you want to find an n0 and c such that for all n ≥ n0,
2k lg n ≤ c 2n
Now, let's let c = 1 and then consider what happens when n = 2m for some m. If we do this, we get
2k lg n ≤ c 2n = 2n
2k lg 2m ≤ 22m
2km ≤ 22m
And, since 2n is a monotonically-increasing function, this is equivalent to
km ≤ 2m
Now, let's finish things off. Let's suppose that we let m = max{k, 4}, so k ≤ m. Thus we have that
km ≤ m2
We also have that
m2 ≤ 2m
Since for any m ≥ 4, m2 ≤ 2m, and we've ensured by our choice of m that m = max{k, 4}. Combining this, we get that
km ≤ 2m
Which is equivalent to what we wanted to show above. Consequently, if we pick any n ≥ 2m = 2max{4, k}, it will be true that nk ≤ 2n. Thus by the formal definition of big-O notation, we get that nk = O(2n).
I think this math is right; please let me know if I'm wrong!
您应该尝试找到一个 n0 和一个 M 来满足此处找到的大 O 表示法的正式定义，而不是像您一直在尝试的那样简化方程：< a href="http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition" rel="nofollow">http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition
一些东西n0=M=k 行可能有效（我还没有写出来，所以也许这行不通，这只是为了给你一个想法）
I can't comment yet, so I will make this an answer.
发布评论
评论（2）
要证明 nk 是 O(2n)，请注意
所以现在你想找到一个 n 0 和 c 使得对于所有 n ≥ n0，
现在，让 c = 1，然后考虑对于某些 m，当 n = 2m 时会发生什么。如果我们这样做，我们会得到
并且，由于 2n 是单调递增函数，因此这相当于
现在，让我们完成任务吧。假设我们让 m = max{k, 4}，因此 k ≤ m。因此我们有
我们也有
因为对于任何 m ≥ 4，m2 ≤ 2m，并且我们有通过我们对 m 的选择确保 m = max{k, 4}。结合这个，我们得到
这相当于我们上面想要显示的内容。因此，如果我们选择任何 n ≥ 2m = 2max{4, k}，则 nk ≤ 2< sup>n。因此，根据大 O 表示法的正式定义，我们得到 nk = O(2n)。
我认为这个数学是正确的；如果我错了，请告诉我！
希望这有帮助！
To show that nk is O(2n), note that
So now you want to find an n0 and c such that for all n ≥ n0,
Now, let's let c = 1 and then consider what happens when n = 2m for some m. If we do this, we get
And, since 2n is a monotonically-increasing function, this is equivalent to
Now, let's finish things off. Let's suppose that we let m = max{k, 4}, so k ≤ m. Thus we have that
We also have that
Since for any m ≥ 4, m2 ≤ 2m, and we've ensured by our choice of m that m = max{k, 4}. Combining this, we get that
Which is equivalent to what we wanted to show above. Consequently, if we pick any n ≥ 2m = 2max{4, k}, it will be true that nk ≤ 2n. Thus by the formal definition of big-O notation, we get that nk = O(2n).
I think this math is right; please let me know if I'm wrong!
Hope this helps!
我还不能发表评论，所以我会回答这个问题。
您应该尝试找到一个
n0和一个M来满足此处找到的大 O 表示法的正式定义，而不是像您一直在尝试的那样简化方程：< a href="http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition" rel="nofollow">http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition一些东西
n0=M=k行可能有效（我还没有写出来，所以也许这行不通，这只是为了给你一个想法）I can't comment yet, so I will make this an answer.
Instead of reducing the equation like you have been trying to do, you should try to find an
n0and aMthat satisfy the formal definition of big O notation found here: http://en.wikipedia.org/wiki/Big_O_notation#Formal_definitionSomething along the lines of
n0=M=kmight work (I haven't written it out so maybe that doesn't work, thats just to give you an idea)