Comment puis-je prouver que 3x $ ^ 3 + 2x + 1 $ est $ \ oméga (x \ cdot \ journal x) $

Question

J'essaie de répondre à cette question: 3 fois $ ^ 3 + 2x + 1 $ est $ \ omega (x \ cdot \ journal x) $

Ma question est de savoir comment résoudre cette question.

Voici ce que j'ai essayé jusqu'à présent:

J'ai appliqué la définition 3 fois $ ^ 3 + 2x + 1> c \ CDOT x \ journal x $ pour tous c, donné $ n \ geq k $ , pour certains k

J'ai essayé d'appliquer la technique d'appliquer l'égalité qui: $ n

Etant donné que n est inférieur au terme de commande le plus élevé, nous pouvons simplement déplacer toutes les conditions pour commander n ??

Donner 6X $

alors vous pouvez choisir: $ k <2 ^ \ frac {6} {c} $

Answer 1

Ce que je recommande d'abord, c'est noter que si vous regardez la complexité de la fonction $ 3 fois ^ 2 + 2x + 1 $ , vraiment tout ce que vous devriez vous soucier est la fonction $ x ^ 2 $ . parce que si vous prouverez que $ x ^ 2=oméga (xlogx) $ Ensuite, ajoutez la 2x $ + 1 $ ne gâchera pas cette preuve depuis $ x ^ 2 $ est polynomiale plus gros que 2 fois + 1 $ et nous pouvons donc simplement regarder la $ x ^ 2 $ . < / p>

(je vais utiliser $ n $ au lieu de $ x $ parce que c'est ce que je suis familier avec mais c'est exactement la même chose pour $ x $ )

Alors maintenant, ce que nous voulons prouver, c'est que $$ n ^ 2=oméga (nlogn) $$

Ce que vous avez offert seulement, vous devez basculer vos côtés dans l'équation, nous devrons trouver un $ C $ , de sorte que pour toute classe N> N_0 $ ou N> K $ K $ : $$ f (n) \ ge c \ cdot g (n) $$ lorsque $ f (n)= n ^ 2 $ , $ g (n)= nlogn $

cela va nous amener à: $ n ^ 2 \ ge cnlogn $

Nous pouvons diviser les deux côtés par $ n $ : $$ N \ GE CLOG $$

Maintenant c'est un peu difficile. mais "on sait" que le temps de fonctionnement polynomial est plus lent que logarithmique.

Fondamentalement, ce que cela signifie que vous préférez atteindre une durée de fonctionnement de la complexité logarithmique si possible parce que vous obtiendrez une exécution plus rapide.

Généralement, il s'agit de l'ordre des heures d'exécution lorsque le premier est le plus rapide:

$$ 1.CONSANT $$ $$ 2.Logarithmic $$ $$ 3.linear $$ $$ 4.Linearithmic $$ $$ 5.polynomial $$ $$ 6.Exponentiel $$

(Vous pouvez en savoir plus ici: https://adrianmejia.com/ plus-popular-algorithms-time-complexity-very-programmer-Hild-nd-Se-Oronline-Tutorial-Course/ )

Une autre façon de voir que c'est si vous trouverez la limite de la division des deux fonctions, disons que nous choisirons: $$ {f (n) \ over g (n)} $$

si $$ \ lim_ {n \ to \ \ \ over g (n)} \ rightarrow \ \ft $$ Cela signifie que $ f (n) $ est "beaucoup plus grand" que $ g (n) $ < / p>

si $$ \ lim_ {n \ to \ infty} {f (n) \ over g (n)} \ rightarrow 0 $$ Cela signifie que $ f (n) $ est "beaucoup plus petit" que $ g (n) $ < / p>

La dernière option (au moins dans cette méthode) est la suivante: $$ \ lim_ {n \ to \ \ \ ot \ over g (n)} \ rightarrow c $$ Quand $ c \ gt 0 $ ce qui signifie que les deux fonctions ont asymptotiquement la même complexité.

retour à nos fonctions, nous pouvons voir que: $$ \ lim_ {n \ to \fty} {n \ over log (n)} $$

Nous allons utiliser la règle lupital et obtenir: $$ \ lim_ {n \ to \ft} {1 \ sur 1 / n} \ RightARrow \ \ \ € $$

Nous pouvons maintenant voir que $ f (n)= n $ est plus gros asymptotiquement à partir de $ g (n)= g (n)= Log (n) $ Par conséquent: $$ n=omega (journal (n)) $$

---

J'espère vraiment que j'ai expliqué aussi clair et facile que possible, c'est juste l'anglais, ce n'est pas ma langue de langue maternelle, donc j'avoue à l'avance pour des erreurs avec Grammer, etc.

---

mise à jour: j'ai remarqué que vous avez apporté des modifications à la fonction d'origine et que c'est maintenant 3 fois $ ^ 3 + 2x + 1 $ , pourtant la preuve Sois la même chose, utilisez simplement $ n ^ 3 $ et que vous obtiendrez toujours le même résultat lorsque vous utilisez Lupital. Que parce que, inévitablement, si nous venions de prouver que $ n ^ 2 $ est beaucoup plus grand que $ log (n) $ < / Span> Bien sûr que $ N ^ 3 $ Ce qui est beaucoup plus grand que $ N ^ 2 $ serait aussi plus gros que $ journal (n). $

Answer 2

Le moyen le plus simple consiste à vérifier que $ \ lim_ {x \ to \ft} \ frac {3x ^ 3 + 2x +1} {x \ journal x}= + \g $ , qui est une condition suffisante pour 3 fois $ ^ 3 + 2x +1 \ in \ \ \ omega (x \ journal x) $

$$ \ lim_ {x \ to \ft} \ frac {3x ^ 3 + 2x +1} {x \ journal x}= \ lim_ {x \ to \ \fty} \ frac {3x ^ 3} {x \ journal x}= \ lim_ {x \ to \fty} \ frac {3x ^ 2} {\ journal x}= \ lim_ {x \ to \fty} 6x ^ 2 = + \ \fty. $$