$ 3X ^ 3 + 2X + 1 $が$ \ omω（x \ cdot \ log x）$です。

Question

この質問に答えようとしています。 $ 3x ^ 3 + 2x + 1 $ は $ \ omomega（x \ cdot \ log x）$ です。

私の質問はこの質問を解決する方法です。

これまでに試したものです：

定義 c \ 3x ^ 3 + 2x + 1> c \ cdot x \ log x $ は、 $ n \ geq k $ 、いくつかのK

私は次のような平等を適用する技術を適用しようとしました。 $ n

nは最高の注文項よりも小さいので、すべての用語を注文することができますか？

$ 6x

それからあなたは選ぶことができます： $ k <2 ^ \ frac {6} {c} $

Answer 1

関数 $ 3x ^ 2 + 2x + 1 $の複雑さを見ている場合に気付くことです。 SPAN>、本当に気にする必要があるすべてのものは、関数 $ x ^ 2 $ です。 の場合、 $ x ^ 2=omomega（xlogx）$ その後、 $ 2x + 1 $ を追加すると、 $ x ^ 2 $ は多項式です。 $ 2x + 1 $ よりも大きいので、 $ x ^ 2 $ を見ることができます。< / P>

（ $ x $ の代わりに $ n $ を使用します。なんあるが $ x $ にはまったく同じです。

だから私たちが証明したいのは、 $$ n ^ 2=omega（nlogn）$$

です。

あなたがどれだけあなたの側を式で裏返す必要があるか、私たちは肯定的な $ c $ を見つける必要があるので、 $ n> n_0 $ または $ n> k $ ： $$ f（n）\ ge c \ cdot g（n）$$ いつ $ f（n）= n ^ 2 $ 、 $ g（n）= nlogn $

それは私たちを得るでしょう： $ n ^ 2 \ ge cnlogn $

$ n $ で両方を分割することができます。 $$ n \ geクローグ$$

今それはトリッキーなものの少しです。 しかし、「多項式走行時間は対数1より遅いことが知られています。

基本的に、それができるのは、可能であれば、可能であれば、対数複雑さの実行時間に到達することをお勧めします。

一般的にこれは、最初が最速の走行時間の順序です。

$$ 1.constant $$ $$ 2.logrommic $$ $$ 3.linear $$ $$ 4.lineArithmic $$ $$ 5.polynomial $$ $$ 6.exponential $$

（ここでそれについてもっと読むことができます。 https://adrianmejia.com/most-popular-algorithms-tim-complexity-every-programmer-should-know-free-online-tutorial-course-tutorial-course-tutorial-course - P>

もう1つの方法で、2つの機能の除算の制限が見つかると、次のように選択しましょう。 $$ {f（n）\ over g（n）} $$

$$ \ lem_ {n \ to \ infty} {f（n）\ over g（n）} \ rightarrow \ infty $$ これは、 $ f（n）$ が $ g（n）$ より「はるかに大きい」です。 / P>

$$ \ lim_ {n \ to \ infty} {f（n）\ over g（n）} \ rightarrow 0 $$ これは、 $ f（n）$ は $ g（n）$ x よりもはるかに小さいです。 / P>

最後のオプション（この方法では少なくとも）は次のとおりです。 $$ \ lim_ {n \ to \ infty} {f（n）\ over g（n）} \ rightarrow c $$ $ c \ gt 0 $ の場合、どちらの関数も同じ複雑さが同じです。

私たちの関数に戻ることはそれを見ることができます： $$ \ lim_ {n \ to \ infty} {n \ over log（n）} $$

ルピータルルールを使い、GET： $$ \ lim_ {n \ to \ infty} {1 \以上1 / n} \ rightarrow \ infty $$

$ f（n）= n $ が $ g（n）=から大きくなるようになりました。 log（n）$ $$ n=omega（log（n））$$

---

私はできるだけ明確で簡単なものとして説明したことを願っています、それは私の母国語の言語ではないので、私はGrammer ETCとの間違いのために事前に謝罪します。

---

Update：元の関数を変更したことに気づいたところ、 $ 3x ^ 3 + 2x + 1 $ 、それでも証明はLumitalを使用しているときに、 $ n ^ 3 $ を使用するだけで、まだ同じ結果が得られます。 必然的に、 $ n ^ 2 $ が $ log（n）$よりもはるかに大きいことを証明した場合/ span>もちろんよりも $ n ^ 3 $ は $ n ^ 2 $ よりもはるかに大きいです。 $ log（n）よりも大きくなるでしょう（n）。$

Answer 2

最も簡単な方法は、 $ \ lim_ {x \ invty} \ frac {3x ^ 3 + 2x + 1} {x \ log x}= + \であることを確認することです。 $ 3x ^ 3 + 2x +1 \ inmega（x \ log x）$ の場合は十分な条件であるinfty $ です。

$$ \ lim_ {x \ \ infty} \ frac {3x ^ 3 + 2x + 1} {x \ log x}= \ lim_ {x \ to \ infty} \ frac {3x ^ 3} {x \ log x}= \ lim_ {x \ infty} \ frac {3x ^ 2} {\ log x}= \ lim_ {x \ to \ infty} 6x ^ 2 = + \ infty。 $$