Esercizio Notazione Asintotica
Ciao a tutti.
Non riesco a capire come risolvere questo esercizio, ho svolto i vari cubi di binomio ma non riesco a trarre la conclusione, qualcuno mio può aiutare?
Quali delle seguenti affermazioni è vera:
a) [tex]n^{3}=\Theta ((n+\log n)^{3})[/tex]
b) [tex]n^{3}=\Theta ((n+ n \log n)^{3})[/tex]
c) [tex]n^{3}=\Theta ((n \log n)^{3})[/tex]
d) [tex]n^{3}=\Theta (n^{3+\log n})[/tex]
Grazie.
Non riesco a capire come risolvere questo esercizio, ho svolto i vari cubi di binomio ma non riesco a trarre la conclusione, qualcuno mio può aiutare?
Quali delle seguenti affermazioni è vera:
a) [tex]n^{3}=\Theta ((n+\log n)^{3})[/tex]
b) [tex]n^{3}=\Theta ((n+ n \log n)^{3})[/tex]
c) [tex]n^{3}=\Theta ((n \log n)^{3})[/tex]
d) [tex]n^{3}=\Theta (n^{3+\log n})[/tex]
Grazie.
Risposte
visto che è un esercizio sì/no, prova ad utilizzare la definizione di confronto asintotico con il limite all'infinito.
Emh..dato che è notazione teta devo applicare la seguente formula:
[tex]c1 g(n)\leq f(n)\leq c2 g(n)[/tex]
la mia [tex]f(n)[/tex] è il cubo di binomio, ma non so cosa mettere e nelle [tex]c1 g(n)[/tex] e [tex]c2 g(n)[/tex] ????
[tex]c1 g(n)\leq f(n)\leq c2 g(n)[/tex]
la mia [tex]f(n)[/tex] è il cubo di binomio, ma non so cosa mettere e nelle [tex]c1 g(n)[/tex] e [tex]c2 g(n)[/tex] ????
Prova a vedere se riesci ad ottenere qualcosa utilizzando il fatto che \( n > \log n \) per ogni \( n \)... In questo modo dovresti riuscire ad ottenere una della due relazioni, mentre l'altra è immediata supponendo che \( n^3 > log n > 0. \)
EDIT: corretta la relazione che lega \(n\) e il logaritmo..
EDIT: corretta la relazione che lega \(n\) e il logaritmo..
Non ho molta dimestichezza quindi non riesco a seguirti nel ragionamento..
Devo sviluppare i vari cubi di binomio che rappresentano la mia [tex]f(n)[/tex]ma non so come minorare e maggiorare poi..
Devo sviluppare i vari cubi di binomio che rappresentano la mia [tex]f(n)[/tex]ma non so come minorare e maggiorare poi..
Ma te l'ho scritto. Se sostituisci \(n\) al logaritmo ottieni una maggiorazione di una di quelle funzioni che puoi sfruttare.
Ho provato a svolgere la prima, ho anche minorato e maggiorato la funzione, ma non sono sicura che si operi in questo modo...
a) [tex]n^{3}=\Theta ((n+\log n)^{3})[/tex]
[tex]n^{3}+ 3n^{2}\log n+3n\log ^{2}n+\log ^{3}n[/tex]
[tex]n^{3}+ 3n^{2}\log n+6n\log n+3\log n[/tex]
[tex]n^{3}\leq c1(n^{3}+3n^{2}\log n)[/tex] che ho provato essere vera per [tex]c=2[/tex] e [tex]n=1[/tex].
[tex]n^{3}\geq c2(6n\log n + 3\log n)[/tex] che ho provato essere vera per [tex]c=1[/tex] e [tex]n=1[/tex].
Quindi dovrebbe essere vera la a).
E' la prima volta che mi cimento con questi esercizi, so la teoria delle notazioni asintotiche ma non so come metterci mano con gli esercizi
a) [tex]n^{3}=\Theta ((n+\log n)^{3})[/tex]
[tex]n^{3}+ 3n^{2}\log n+3n\log ^{2}n+\log ^{3}n[/tex]
[tex]n^{3}+ 3n^{2}\log n+6n\log n+3\log n[/tex]
[tex]n^{3}\leq c1(n^{3}+3n^{2}\log n)[/tex] che ho provato essere vera per [tex]c=2[/tex] e [tex]n=1[/tex].
[tex]n^{3}\geq c2(6n\log n + 3\log n)[/tex] che ho provato essere vera per [tex]c=1[/tex] e [tex]n=1[/tex].
Quindi dovrebbe essere vera la a).
E' la prima volta che mi cimento con questi esercizi, so la teoria delle notazioni asintotiche ma non so come metterci mano con gli esercizi
[SP (Solo Per)]:
La definizione del confronto asinstotico con il limite, che forse non conosci, è questa:
$\lim_{n->oo} f(n)/g(n) = {(0\ \Rightarrow\ f(n) \in o(g(n))),(c\ \Rightarrow\ f(n) \in \Theta(g(n))),(oo\ \Rightarrow\ f(n) \in \omega(g(n))):}$
basta che guardi il secondo caso.
[/SP]
La definizione del confronto asinstotico con il limite, che forse non conosci, è questa:
$\lim_{n->oo} f(n)/g(n) = {(0\ \Rightarrow\ f(n) \in o(g(n))),(c\ \Rightarrow\ f(n) \in \Theta(g(n))),(oo\ \Rightarrow\ f(n) \in \omega(g(n))):}$
basta che guardi il secondo caso.
[/SP]
Emh..vediamo se ho capito bene.
Allora:
a) [tex]\frac{n^{3}}{3n^{2}\log n+3n \log ^{2}n+\log ^{3}n }[/tex] la f(n) è di ordine superiore a g(n) e quindi è falsa.
b) [tex]\frac{n^{3}}{3n^{3}\log n+3n^{3}\log ^{2}n+n^{3}\log ^{3}n}[/tex] la f(n) e g(n) sono dello stesso ordine e quindi è vera.
c) [tex]\frac{n^{3}}{\log ^{3}n}[/tex] la mia f(n) è di ordine superiore a g(n) e quindi è falsa.
d) [tex]\frac{n^{3}}{\log ^{3}n}[/tex] la mia f(n) è di ordine superiore a g(n) e quindi è falsa.
Corretto?
Allora:
a) [tex]\frac{n^{3}}{3n^{2}\log n+3n \log ^{2}n+\log ^{3}n }[/tex] la f(n) è di ordine superiore a g(n) e quindi è falsa.
b) [tex]\frac{n^{3}}{3n^{3}\log n+3n^{3}\log ^{2}n+n^{3}\log ^{3}n}[/tex] la f(n) e g(n) sono dello stesso ordine e quindi è vera.
c) [tex]\frac{n^{3}}{\log ^{3}n}[/tex] la mia f(n) è di ordine superiore a g(n) e quindi è falsa.
d) [tex]\frac{n^{3}}{\log ^{3}n}[/tex] la mia f(n) è di ordine superiore a g(n) e quindi è falsa.
Corretto?
Ma non mancano dei termini nei tuoi denominatori?
Allora, dopo aver sviluppato i vari cubi di binomio ottengo:
a) [tex]{n^{3}+3n^{2} \log n+3n\log ^{2}n +\log ^{3}n}[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]1+\frac{n}{3\log n}+\frac{n^{2}}{3\log ^{2}n}+\frac{n^{3}}{\log ^{3}n}[/tex]
b) [tex]{n^{3}+n^{3} \log ^{3}n+3n^{3}\log n+3n^{3}\log ^{2}n}[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]1+\frac{1}{\log ^{3}n}+\frac{1}{3\log n}+\frac{1}{3\log ^{2}n}[/tex]
c) [tex]n^{3}\log ^{3}n[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]\frac{1}{\log ^{3}n}[/tex]
d) [tex]n^{3}n^{\log n}[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]\frac{1}{n^{\log n}}[/tex]
Dato che l' [tex]n^{3}[/tex] compare solo nella a) possiamo dire che questa è vera.
Giusto?
a) [tex]{n^{3}+3n^{2} \log n+3n\log ^{2}n +\log ^{3}n}[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]1+\frac{n}{3\log n}+\frac{n^{2}}{3\log ^{2}n}+\frac{n^{3}}{\log ^{3}n}[/tex]
b) [tex]{n^{3}+n^{3} \log ^{3}n+3n^{3}\log n+3n^{3}\log ^{2}n}[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]1+\frac{1}{\log ^{3}n}+\frac{1}{3\log n}+\frac{1}{3\log ^{2}n}[/tex]
c) [tex]n^{3}\log ^{3}n[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]\frac{1}{\log ^{3}n}[/tex]
d) [tex]n^{3}n^{\log n}[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]\frac{1}{n^{\log n}}[/tex]
Dato che l' [tex]n^{3}[/tex] compare solo nella a) possiamo dire che questa è vera.
Giusto?
ma scusa hai mai calcolato un limite??
prendiamo il b):
non mi pare proprio tu possa fare una cosa del genere.
Forse non ha compreso cosa bisogna fare:
$n^3\ in^?\ \Theta((n +nlog(n))^3)$
proviamo con il confronto asintotico:
- $f(n) = n^3$
- $g(n) = (n +nlog(n))^3$
$lim_{n -> oo} f(n)/g(n) = lim_{n -> oo} n^3/(n +nlog(n))^3 =$
$= n^3/{n^{3}+n^{3} \log ^{3}n+3n^{3}\log n+3n^{3}\log ^{2}n} = n^3/{n^3(1+\log ^{3}n+3\log n+3\log ^{2}n)} = $
$= 1/(1+\log ^{3}n+3\log n+3\log ^{2}n) -> 0 \Rightarrow o((n +nlog(n))^3)$ perciò è falso.
comunque alla fine questo metodo non è tanto più veloce dell'altro, è solo un'alternativa.
prendiamo il b):
b) [tex]{n^{3}+n^{3} \log ^{3}n+3n^{3}\log n+3n^{3}\log ^{2}n}[/tex]
divido ogni membro per [tex]n^{3}[/tex] e mi rimane:
[tex]1+\frac{1}{\log ^{3}n}+\frac{1}{3\log n}+\frac{1}{3\log ^{2}n}[/tex]
non mi pare proprio tu possa fare una cosa del genere.
Forse non ha compreso cosa bisogna fare:
$n^3\ in^?\ \Theta((n +nlog(n))^3)$
proviamo con il confronto asintotico:
- $f(n) = n^3$
- $g(n) = (n +nlog(n))^3$
$lim_{n -> oo} f(n)/g(n) = lim_{n -> oo} n^3/(n +nlog(n))^3 =$
$= n^3/{n^{3}+n^{3} \log ^{3}n+3n^{3}\log n+3n^{3}\log ^{2}n} = n^3/{n^3(1+\log ^{3}n+3\log n+3\log ^{2}n)} = $
$= 1/(1+\log ^{3}n+3\log n+3\log ^{2}n) -> 0 \Rightarrow o((n +nlog(n))^3)$ perciò è falso.
comunque alla fine questo metodo non è tanto più veloce dell'altro, è solo un'alternativa.
Grazie infinite, adesso ho capito! 
Siccome la soluzione è stata in effetti ormai data, mostro i calcoli che avevo in mente con il mio precedente consiglio di considerare che \( n > \log n \) per ogni \(n\). Si ottiene in particolare immediatamente che \( (n + \log n)^3 < (2\,n)^3 < 8\,n^3 \) da cui si ottiene una prima relazione: \( 1/8 (n + \log n)^3 < n^3. \) D'altra parte, abbiamo che \( (n + \log n)^3 > n^3 \) per ogni \( n > 2 \). Per cui otteniamo che
\[ 1/8 (n + \log n)^3 < n^3 < (n + \log n)^3. \]
In tutti gli altri casi si poteva riscrivere l'espressione nella forma \( h(n)\,n^3 \) dove \(h(n)\) era una qualche funzione non limitata e monotona crescente. Si poteva quindi osservare che non era possibile trovare una costante \( c \) per cui \( c\,n^3 > h(n)\,n^3 \) in quando non esisteva alcuna costante per cui \( c > h(n) \) per ogni \(n\) sufficientemente grande in quanto \( \lim_{n \to \infty} h(n) = \infty \) in tutti i casi.
\[ 1/8 (n + \log n)^3 < n^3 < (n + \log n)^3. \]
In tutti gli altri casi si poteva riscrivere l'espressione nella forma \( h(n)\,n^3 \) dove \(h(n)\) era una qualche funzione non limitata e monotona crescente. Si poteva quindi osservare che non era possibile trovare una costante \( c \) per cui \( c\,n^3 > h(n)\,n^3 \) in quando non esisteva alcuna costante per cui \( c > h(n) \) per ogni \(n\) sufficientemente grande in quanto \( \lim_{n \to \infty} h(n) = \infty \) in tutti i casi.
"apatriarca":
Siccome la soluzione è stata in effetti ormai data, mostro i calcoli che avevo in mente con il mio precedente consiglio di considerare che \( n > \log n \) per ogni \(n\). Si ottiene in particolare immediatamente che \( (n + \log n)^3 < (2\,n)^3 < 8\,n^3 \) da cui si ottiene una prima relazione: \( 1/8 (n + \log n)^3 < n^3. \) D'altra parte, abbiamo che \( (n + \log n)^3 > n^3 \) per ogni \( n > 2 \). Per cui otteniamo che
\[ 1/8 (n + \log n)^3 < n^3 < (n + \log n)^3. \]
In tutti gli altri casi si poteva riscrivere l'espressione nella forma \( h(n)\,n^3 \) dove \(h(n)\) era una qualche funzione non limitata e monotona crescente. Si poteva quindi osservare che non era possibile trovare una costante \( c \) per cui \( c\,n^3 > h(n)\,n^3 \) in quando non esisteva alcuna costante per cui \( c > h(n) \) per ogni \(n\) sufficientemente grande in quanto \( \lim_{n \to \infty} h(n) = \infty \) in tutti i casi.
un metodo più raffinato utilizzare la definizione, così si trovano anche le costanti.
comunque non volevo sovrapporti, diciamo che abbiam dato più metodi per arrivare alla soluzione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo