関数f(n)がビッグテタ(g(n))に属することを証明する
-
01-10-2019 - |
質問
クラスのビッグテタ(g(n))を示すように求める演習は、機能が属し、アサーションを証明するためです。
この場合、f(n)=(n^2+1)^10
定義により、f(n)e big-theta(g(n))<=> c1*g(n)<f(n)<c2*g(n)。ここで、c1とc2は2つの定数です。
この特定のf(n)では、ビッグテタはg(n^20)であることを知っていますが、誰が適切に証明するかわかりません。私はこの不平等を操作する必要があると思いますが、方法がわかりません
解決
関数f(x)はθ(g(x))です。
- f(x)はo(g(x))であり、
- g(x)はo(f(x))です
したがって、単一の不平等でそれを証明しようとすることができますが、これらの2つの部分に分解することをお勧めします。最初に、いくつかのn> nについてそれを証明します0 f(n)<c1 g(n)、そしていくつかのn> nについてそれを証明します0 g(n)<c2 f(n)。両方の部分を証明したら、個別に、θの定義に戻ってf =θ(g)を証明できます。
他のヒント
私はこれについては本当に専門家ではありませんが、F(n)eο(n)とf(n)eω(n)を証明することはできませんでした。交差点の定義のために?
所属していません StackOverflow