如何证明这种大表示法?

本文介绍了如何证明这种大表示法?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如何证明这一点:

4 n = O(8 n )

8 n = O(4 n )?

4n = O(8n)

8n = O(4n)?

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

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

推荐答案

我试图澄清一下……

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

1. For a proof (see formal definition of Big-O) we have to find any C and n0, that 4n <= C * 8n 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 n 和g(n)= 8 n

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

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 ... ^^