Wie beweise ich, dass $ 3x ^ 3 + 2x + 1 $ $ \ omega (x \ cdot \ log x) $

Question

Ich versuche, diese Frage zu beantworten: $ 3x ^ 3 + 2x + 1 $ ist $ \ omega (x \ cdot \ log x) $

Meine Frage ist, wie Sie diese Frage lösen können.

Hier habe ich bisher versucht:

Ich habe die Definition aufgetragen $ 3x ^ 3 + 2x + 1> c \ cdot x \ log x $ für alle c, angegeben $ n \ geq k $ , für ein paar k

Ich habe versucht, die Technik der Anwenden der Gleichstellung anzuwenden, die: $ n

Da n weniger als der höchste Reihenfolge ist, können wir nur alle Bedingungen auf Bestellung n ??

bewegen

Geben $ 6x

Dann können Sie wählen: $ k <2 ^ \ frac {6} {c} $

Answer 1

was ich empfehle, ist zuerst zu bemerken, dass, wenn Sie die Komplexität der Funktion $ 3x ^ 2 + 2x + 1 $ , wirklich alles, was Sie interessieren, ist die Funktion $ x ^ 2 $ . weil wenn Sie belegen, dass $ x ^ 2=omega (xlogx) $ Hinzufügen der $ 2x + 1 $ wird diesen Beweis nicht ruinieren, da $ x ^ 2 $ Polynomial ist Größerer als $ 2x + 1 $ und so können wir einfach den $ x ^ 2 $ ansehen. < / p>

(ich werde $ n $ anstelle von $ x $ , weil das ist, was ich bin vertraut, aber es ist genau das gleiche für $ x $ )

also, was wir jetzt beweisen wollen, ist, dass $$ n ^ 2=omega (nlogn) $$

Wenn Sie nur angeboten haben, müssen Sie Ihre Seiten in der Gleichung umdrehen, müssen wir einen positiven $ C $ finden, so dass für jede $ n> n_0 $ oder $ n> k $ : $$ f (n) \ ge c \ cdot g (n) $$ wann $ f (n)= n ^ 2 $ , $ g (n)= nlogn $ .

das bringt uns zu: $ n ^ 2 \ ge cnlogn $

Wir können beide Seite mit $ N $ teilen: $$ N \ GE CLOGN $$

Jetzt ist das ein bisschen ein Schwierigkeiten. Aber "es ist bekannt", dass die Polynomlaufzeit langsamer ist als logarithmisch.

Grundsätzlich, was bedeutet, dass Sie möchten, dass Sie es vorziehen, wenn möglich, wenn Sie möglich sind, da Sie eine schnellere Ausführung erhalten.

Im Allgemeinen ist dies die Reihenfolge der Laufzeiten, in denen der erste das schnellste ist:

$$ 1.constant $$ $$ 2.logarithmisch $$ $$ 3.linear $$ $$ 4.Linearithmic $$ $$ 5.Polynomial $$ $$ 6.Exponential $$

(Sie können hier mehr darüber erfahren: https://adrianmejia.com/most-popular-algorithms-time-complexity-eewy-programmer-should-know-free-online-tutorial-course/ )

Eine andere Möglichkeit, es zu sehen, ist, wenn Sie das Limit der Division der beiden Funktionen finden, sagen wir, wir wählen: $$ {f (n) \ über g (n)} $$

wenn $$ \ lim_ {n \ to \ fly} {f (n) \ über g (n)} \ RightArrow \ Infty $$ Es bedeutet, dass $ F (n) $ "viel größer" ist als $ g (n) $ < / p>

wenn $$ \ lim_ {n \ to \ Infty} {f (n) \ über g (n)} \ rightarrow 0 $$ Es bedeutet, dass $ F (n) $ "viel kleiner" als $ g (n) $

Die letzte Option (zumindest in dieser Methode) ist: $$ \ lim_ {n \ to \ Infty} {f (n) \ über g (n)} \ Rightarrow C $$ Wenn $ c \ gt 0 $ , was bedeutet, dass beide Funktionen asymptotisch die gleiche Komplexität haben.

Zurück zu unseren Funktionen, wir können das sehen: $$ \ lim_ {n \ to \ Infty} {n \ over Log (n)} $$

Wir werden die Lupiditalregel verwenden und: $$ \ LIM_ {n \ to \ Infty} {1 \ über 1 / N} \ Rightarrow \ Infty $$

Wir können jetzt sehen, dass $ f (n)= n $ größer asymptotisch von $ g (n)= log (n) $ somit: $$ n=omega (log (n)) $$

---

Ich hoffe wirklich, dass ich so klar und einfach erklärt habe, dass es nur Englisch ist, ist nur Englisch nicht meine Muttersprachesprache, also apaste ich im Voraus für Fehler mit GRAMMER usw.

---

update: Ich habe bemerkt, dass Sie Änderungen an der Originalfunktion vorgenommen haben, und jetzt ist es $ 3x ^ 3 + 2x + 1 $ , doch der Beweis wird Seien Sie dasselbe, verwenden Sie einfach $ N ^ 3 $ und dann erhalten Sie immer noch dasselbe Ergebnis, wenn Sie Lupital verwenden. Das, weil zwangsläufig, wenn wir gerade bewiesen haben, dass $ n ^ 2 $ viel größer ist als $ log (n) $ < / span> als natürlich, dass $ n ^ 3 $ viel größer als $ n ^ 2 $ wäre auch größer als $ log (n). $

Answer 2

Der einfachste Weg ist, diesen $ \ lim_ {x \ to \ fly} \ frac {3x ^ 3 + 2x +1} {x \ log x}= + \Infty $ , ein ausreichender Bedingung für $ 3x ^ 3 + 2x +1 \ in \ omega (x \ log x) $ .

.

$$ \ lim_ {x \ to \ Infty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= \ lim_ {x \ to \ Infty} \ frac {3x ^ 3} {x \ log x}= \ lim_ {x \ to \ fly} \ frac {3x ^ 2} {\ log x}= \ lim_ {x \ to \ fly} 6x ^ 2 = + \ fanty. $$