time-complexity - 特定の機能のビッグシータ、ビッグO、ビッグオメガ

Question

関数Fを考えてみましょう：2 ^（3 * n）+ n ^ 2

関数A：2 ^（3 * n）は、Fの特性としてビッグシータ、オメガ、またはOとして使用できますか？なんで？

Big Omega、Big Theta、Big Oの概念を改訂していて、この例に出くわしましたが、どこから始めればよいのかわかりません。

Answer 1

いいえ。

2^(3*n) が主要な用語ですが、何か非常に間違ったことをしていない限り、計算にそれほど時間はかかりません。ウィキペディアには、さまざまな関数の時間計算量の優れたリストがあります。あなたがしている最も複雑な操作は累乗であり、その複雑さは他の投稿で議論されています。

g(x) = 2^x および f(x) = 3x の形式 g(f(x)) の関数を見ているので、計算時間は O(h) + O(ここで、h は g の時間計算量、k は f の時間計算量です。考えてみてください。操作を 2 つに分けて、部分を別々に行うことで時間を節約できるのであれば、これ以上にすることはできません。h がこの合計を支配するため、通常は k 項をオフのままにします。

Answer 2

はい、3 つすべてです。一般に、成長の遅い用語は成長の速い用語に「圧倒」されるため、最も急速に成長する用語にのみ注意を払う必要があります。

詳細に：

明らかに F は A より速く成長するので、 F \in \Omega(A) は簡単です。すべての十分に大きな n に対して、F より小さい A の正の倍数 (つまり、A 自体) が存在します。

F を 2*A に対してプロットしてみてください。2*A が F よりも急速に大きくなり、そのままであることがわかります。したがって、引数が十分に大きい場合、F よりも大きい A の正の倍数 (つまり 2*A) が存在します。したがって、O, F \in O(A) の定義によります。

最後に、F \in \Omega(A) および F \in O(A) であるため、F \in \Theta(A) です。