[Algoritmi] Esercitazione sulla notazione asintotica
Ciao a tutti!
Sto svolgendo un esercizio dove devo indicare se vale $f(n)=O(g(n))$, o se $f(n)=\Omega(g(n))$, oppure se valgono entrambe le condizioni $f(n)=\Theta(g(n))$, volevo essere confermato che il mio ragionamento sia esatto.
Per esempio ho queste due funzioni:
$f(n)=n-sqrt(n) * log (n)$ , $g(n)=5n+2sqrt(n)log^3n$
Poiché $f(n) = O(n)$ e $g(n)=O(n)$ allora $f(n)=\Theta(g(n))$
Oppure per queste altre funzioni:
$f(n)=10n log^4 n$ , $g(n)=(n/10)root(3)(n)$
Poiché $f(n) = O(n log n)$ e $g(n)=O(n)$ allora $f(n)=\Omega(g(n))$
O ancora:
$f(n)=n^(3/2) - n log n$ , $g(n)=8n*log^3 n$
Poiché $f(n) = O(sqrt(n))$ e $g(n)=O(n log n)$ allora $f(n)=\O(g(n))$
Però su quest'ultima ad essere sincero non so se considerare f(n) una polinomiale poiché l'esponente è >= 1 oppure un radicale...
Io comunque utilizzo la seguente scaletta, per stabilire l'ordine di grandezza di una funzione:
$O(1) , O(log log n) , O(log n) , O( root(c) n) con (c > 1) , O(n) , O(n log n)$
$O(n^2 ) , O(n^3 ) , O(n^k ) con (k ≥ 1) , O(a^n ) con (a > 1) , O(n!)$
Spero di essere stato chiaro, grazie.
Sto svolgendo un esercizio dove devo indicare se vale $f(n)=O(g(n))$, o se $f(n)=\Omega(g(n))$, oppure se valgono entrambe le condizioni $f(n)=\Theta(g(n))$, volevo essere confermato che il mio ragionamento sia esatto.
Per esempio ho queste due funzioni:
$f(n)=n-sqrt(n) * log (n)$ , $g(n)=5n+2sqrt(n)log^3n$
Poiché $f(n) = O(n)$ e $g(n)=O(n)$ allora $f(n)=\Theta(g(n))$
Oppure per queste altre funzioni:
$f(n)=10n log^4 n$ , $g(n)=(n/10)root(3)(n)$
Poiché $f(n) = O(n log n)$ e $g(n)=O(n)$ allora $f(n)=\Omega(g(n))$
O ancora:
$f(n)=n^(3/2) - n log n$ , $g(n)=8n*log^3 n$
Poiché $f(n) = O(sqrt(n))$ e $g(n)=O(n log n)$ allora $f(n)=\O(g(n))$
Però su quest'ultima ad essere sincero non so se considerare f(n) una polinomiale poiché l'esponente è >= 1 oppure un radicale...
Io comunque utilizzo la seguente scaletta, per stabilire l'ordine di grandezza di una funzione:
$O(1) , O(log log n) , O(log n) , O( root(c) n) con (c > 1) , O(n) , O(n log n)$
$O(n^2 ) , O(n^3 ) , O(n^k ) con (k ≥ 1) , O(a^n ) con (a > 1) , O(n!)$
Spero di essere stato chiaro, grazie.
Risposte
"Skeggia":
Ciao a tutti!
Sto svolgendo un esercizio dove devo indicare se vale $f(n)=O(g(n))$, o se $f(n)=\Omega(g(n))$, oppure se valgono entrambe le condizioni $f(n)=\Theta(g(n))$, volevo essere confermato che il mio ragionamento sia esatto.
su cosa hai basato queste appartenenze, hai utilizzato una dimostrazione simil induzione, cose più veloci come passaggio al limite?
Ciao hamming e grazie!
Sinceramente non ho capito se vuoi sapere da dove derivano $f(n)=O(g(n))$,$f(n)=\Omega(g(n))$ e $f(n)=\Theta(g(n))$ oppure come mi sono basato per stabilire a cosa appartengono f(n) e g(n).
Se ti riferisci a quest'ultima cosa, mi sono basato sulla scaletta che ho messo in fondo al post dove man mano che si scende troviamo funzioni che crescono più velocemente (in senso stretto). Per ogni funzione considero quella che cresce più velocemente e dopodiché le confronto. Si potrebbe fare anche $lim_{n \to \infty}f(n)/g(n)$ e se ottengo una costante $c != 0$ allora è $f(n)=\Theta(g(n))$ se ottengo $0$ allora $f(n)=O(g(n))$, se ottengo $infty$ allora $f(n)=\Omega(g(n))$. Però il prof ci consiglia di fare il limite, solo nel caso in cui alcune regole (tra cui la scaletta) fallissero, insomma come ultima spiaggia. Ma il problema è che non sono sicuro di far bene.
Sinceramente non ho capito se vuoi sapere da dove derivano $f(n)=O(g(n))$,$f(n)=\Omega(g(n))$ e $f(n)=\Theta(g(n))$ oppure come mi sono basato per stabilire a cosa appartengono f(n) e g(n).
Se ti riferisci a quest'ultima cosa, mi sono basato sulla scaletta che ho messo in fondo al post dove man mano che si scende troviamo funzioni che crescono più velocemente (in senso stretto). Per ogni funzione considero quella che cresce più velocemente e dopodiché le confronto. Si potrebbe fare anche $lim_{n \to \infty}f(n)/g(n)$ e se ottengo una costante $c != 0$ allora è $f(n)=\Theta(g(n))$ se ottengo $0$ allora $f(n)=O(g(n))$, se ottengo $infty$ allora $f(n)=\Omega(g(n))$. Però il prof ci consiglia di fare il limite, solo nel caso in cui alcune regole (tra cui la scaletta) fallissero, insomma come ultima spiaggia. Ma il problema è che non sono sicuro di far bene.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo