如何证明这种大表示法? [英] How to prove this statement of big o notation?

问题描述

如何证明这一点:

1. 4 ⁿ = O(8 ⁿ )
2. 8 ⁿ = O(4 ⁿ )?

1. 4ⁿ = O(8ⁿ)
2. 8ⁿ = O(4ⁿ)?

那两种情况下的C和n0值是什么?

So what are the C and n0 values for both cases?

推荐答案

我试图澄清一下……

1. 作为证明(请参见 Big-O的正式定义)，我们必须找到任何和n0，对于所有n> n0来说，4 ⁿ < = C * 8 ⁿ . 所以-为了证明您的情况1，全都在于找到这两个值的示例.我们将尝试...我刚刚从维基百科引用的方程式说:

1. For a proof (see formal definition of Big-O) we have to find any C and n0, that 4ⁿ <= C * 8ⁿ for all n > n0. So - to prove your case 1 it is all about finding an example for these two values. We will try ... the equation I just quoted from wikipedia says:

f(n) = O(g(n))

当且仅当存在一个正实数C和一个实数n0这样

|f(n)| <= C * |g(n)| for all n > n0

其中f(n)= 4 ⁿ 和g(n)= 8 ⁿ

where f(n) = 4ⁿ and g(n)=8ⁿ

4^n    <= C * 8^n
4^n    <= C * 2^n * 4^n
1      <= C * 2^n

所以我们也选择C为1和n0为1.该方程式是正确的->已证明案例1.

So we choose C to be 1 and n0 to be 1, too. The equation is true -> case 1 proven.

2. 我想这是家庭作业-您应该自己尝试一下-只要您提供自己的尝试结果，我就能为您提供更多帮助.
提示:也可以尝试在那里找到一个C和n0-也许您可以证明，方程... ^^

2. Since I guess, that this is homework - you should give it a try yourself - I can help you a bit more, as soon as you provide results of your own tries.
Hint: just try to find a C and a n0 there, too - maybe you can prove, that there never exists any pair of C and n0 for the equation ... ^^

这篇关于如何证明这种大表示法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！