Come dimostrano che $ 3x ^ 3 + 2x + 1 $ è $ \ omega (x \ cdot \ log x) $

Question

Sto cercando di rispondere a questa domanda: $ 3x ^ 3 + 2x + 1 $ è $ \ omega (x \ cdot \ log x) $

La mia domanda è come risolvere questa domanda.

Ecco cosa ho provato finora:

ho applicato la definizione $ 3x ^ 3 + 2x + 1> c \ cdot x \ log x $ per tutto c, data $ n \ GeQ k $ , per alcuni k

Ho provato ad applicare la tecnica di applicare l'uguaglianza che: $ n

Dal momento che n è inferiore al termine di ordine più alto che possiamo semplicemente spostare tutti i termini per ordinare n ??

dando $ 6x

Allora puoi scegliere: $ k <2 ^ \ frac {6} {c} $

Answer 1

Quello che consiglio prima è notare che se stai guardando la complessità della funzione $ 3x ^ 2 + 2x + 1 $ , Davvero tutto ciò che dovresti preoccuparti è la funzione $ x ^ 2 $ . Perché Se dimostrerai quella $ x ^ 2=Omega (XLOGX) $ quindi aggiungere la classe $ 2x + 1 $ non rovina quella prova da $ x ^ 2 $ è polinomialmente Più grande di $ 2x + 1 $ e quindi possiamo solo guardare la $ x ^ 2 $ . < / P >.

(utilizzerò $ N $ invece di $ x $ perché è quello che sono familiarità con ma è esattamente la stessa per $ x $ )

Così ora ciò che vogliamo dimostrare è che $$ n ^ 2=omega (nlogn) $$

Quale come ti è stato offerto solo di aver bisogno di lanciare i lati nell'equazione, avremo bisogno di trovare una classe Positive $ c $ , così per qualsiasi classe $ n> n_0 $ o $ n> k $ : $$ f (n) \ ge c \ clot g (n) $$ quando $ f (n)= n ^ 2 $ , $ g (n)= nlogh $ che ci porterà a: $ n ^ 2 \ ge cnlogns $

Possiamo dividere entrambi i lati da $ n $ : $$ n \ Ge clon $$

Ora è un po 'ingannato. Ma "è noto" che il tempo di esecuzione polinomiale è più lento del logaritmico.

Fondamentalmente ciò che significa è che preferiresti raggiungere una complessità logaritmica in esecuzione il tempo in esecuzione, se possibile, perché riceverai un'esecuzione più rapida.

Generalmente questo è l'ordine dei tempi di esecuzione quando il primo è il più veloce:

$$ 1.constant $$ $$ 2.Logarithmic $$ $$ 3.linear $$ $$ 4.linearithmic $$ $$ 5.polynomial $$ $$ 6exponentive $$

(Puoi leggere di più qui: https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-Should-Know-Free-online-tutorial-course/ ) .

Un altro modo per vedere è se troverai il limite della divisione delle due funzioni, diciamo che sceglieremo: $$ {f (n) \ over g (n)} $$

Se $$ \ lim_ {n \ to \ infty} {f (n) \ over g (n)} \ reapyarrow \ Infty $$ Significa che $ f (n) $ è "molto più grande" di $ g (n) $ < / P >.

Se $$ \ lim_ {n \ to \ infty} {f (n) \ over g (n)} \ dama dameprow 0 $$ Significa che $ f (n) $ è "molto più piccolo" di $ g (n) $ < / P >.

L'ultima opzione (almeno in questo metodo) è: $$ \ LIM_ {n \ to \ INFTY} {F (N) \ Over G (N)} \ RightArrow C $$ Quando $ c \ GT 0 $ Il che significa che entrambe le funzioni hanno asintoticamente la stessa complessità.

Torna alle nostre funzioni, possiamo vedere che: $$ \ LIM_ {n \ to \ Infty} {n \ over log (n)} $$

Useremo la regola lupitale e ottenere: $$ \ LIM_ {n \ to \ INFTY} {1 \ Over 1 / N} \ RightArrow \ INFTY $$

Ora possiamo vedere quella $ f (n)= n $ è più grande asintoticamente da $ g (n)= Log (n) $ Quindi: $$ n=omega (log (n)) $$

---

.

Spero davvero di aver spiegato il più chiaro e facile possibile, è solo l'inglese non è la mia lingua madre della mia madre, quindi ho apolegibile in anticipo per eventuali errori con grammer ecc.

---

.

Aggiornamento: ho notato che hai apportato modifiche alla funzione originale e ora è $ 3x ^ 3 + 2x + 1 $ , tuttavia la prova lo farà Sii lo stesso, basta usare $ n ^ 3 $ e di quanto tu abbia ancora lo stesso risultato quando usi lupital. Questo perché, inevitabilmente, se abbiamo appena dimostrato che $ n ^ 2 $ è molto più grande di $ log (n) $ < / span> che ovviamente che $ n ^ 3 $ che è molto più grande di $ n ^ 2 $ sarebbe anche più grande di $ log (n). $

Answer 2

Il modo più semplice è verificare che $ \ lim_ {x \ to \ infty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= + \INFTY $ , che è una condizione sufficiente per $ 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 \ infty} \ frac {3x ^ 2} {\ log x}= \ lim_ {x \ to \ infty} 6x ^ 2 = + \ INFTY. $$