Utilizzo dei simboli di Landau "a sè stanti"?
Cerco di spiegarmi meglio visto che il titolo forse non è dei migliori.
Sto studiando i simboli di Landau, e ho dei dubbi riguardo tutti gli altri simboli eccetto asintotico e o-piccolo (quindi O-grande ecc.).
Innanzitutto scrivo qui quello che ho capito dell'o-piccolo, in modo da chiedere conferma a voi di aver capito un po' cosa rappresenta/come funziona.
Data la definizione di o-piccolo come : \(\displaystyle an = o(bn) \) se lim x->+inf \(\displaystyle an/bn = 0 \)
Di conseguenza se trovo o-piccolo in una situazione tipo \(\displaystyle x^4 + x^2 + o(x^3) \) dovrei poter semplificare in \(\displaystyle x^4 + o(x^3) \) essendo \(\displaystyle x^2 = o(x^3) \), quindi posso vedere l'o-piccolo di X come la classe che contiene tutti i numeri inferiori a quel determinato numero X, in quanto facendo il rapporto tendente a infinito tra un numero inferiore a X e X stesso, tenderà sempre a 0. Non so se mi sono spiegato bene, spero di sì
Ora, il mio problema deriva per esempio da O-grande. So che la definizione di O-grande dice che \(\displaystyle an=O(bn) \) se lim x->+inf \(\displaystyle an <= C|bn| \)definitivamente.
Ecco, al contrario dell'o-piccolo però, non capisco come interpretarlo/utilizzarlo in situazioni in cui non è presente la relazione an=O(bn).
Per esempio ho un esercizio dove verificare se le affermazioni sono vere o false, e ho:
\(\displaystyle n logn + O(n^2)\) asintotico a \(\displaystyle nlogn \).
Procedo allora calcolando \(\displaystyle (nlogn+O(n^2))/nlogn \) che mi diventa \(\displaystyle nlogn/nlogn + O(n^2)/nlogn \) ---> \(\displaystyle 1 + O(n^2)/nlogn \). Arrivato a questo punto non capisco come interpretare \(\displaystyle O(n^2) \). Se fosse un o-piccolo saprei cosa rappresenta, e se non ho capito male \(\displaystyle o(n^2) > nlogn \) e di conseguenza tenderebbe a +infinito per x-> + infinito.
Ma con l'O-grande?
Spero di non essere stato troppo confuso!
Sto studiando i simboli di Landau, e ho dei dubbi riguardo tutti gli altri simboli eccetto asintotico e o-piccolo (quindi O-grande ecc.).
Innanzitutto scrivo qui quello che ho capito dell'o-piccolo, in modo da chiedere conferma a voi di aver capito un po' cosa rappresenta/come funziona.
Data la definizione di o-piccolo come : \(\displaystyle an = o(bn) \) se lim x->+inf \(\displaystyle an/bn = 0 \)
Di conseguenza se trovo o-piccolo in una situazione tipo \(\displaystyle x^4 + x^2 + o(x^3) \) dovrei poter semplificare in \(\displaystyle x^4 + o(x^3) \) essendo \(\displaystyle x^2 = o(x^3) \), quindi posso vedere l'o-piccolo di X come la classe che contiene tutti i numeri inferiori a quel determinato numero X, in quanto facendo il rapporto tendente a infinito tra un numero inferiore a X e X stesso, tenderà sempre a 0. Non so se mi sono spiegato bene, spero di sì
Ora, il mio problema deriva per esempio da O-grande. So che la definizione di O-grande dice che \(\displaystyle an=O(bn) \) se lim x->+inf \(\displaystyle an <= C|bn| \)definitivamente.
Ecco, al contrario dell'o-piccolo però, non capisco come interpretarlo/utilizzarlo in situazioni in cui non è presente la relazione an=O(bn).
Per esempio ho un esercizio dove verificare se le affermazioni sono vere o false, e ho:
\(\displaystyle n logn + O(n^2)\) asintotico a \(\displaystyle nlogn \).
Procedo allora calcolando \(\displaystyle (nlogn+O(n^2))/nlogn \) che mi diventa \(\displaystyle nlogn/nlogn + O(n^2)/nlogn \) ---> \(\displaystyle 1 + O(n^2)/nlogn \). Arrivato a questo punto non capisco come interpretare \(\displaystyle O(n^2) \). Se fosse un o-piccolo saprei cosa rappresenta, e se non ho capito male \(\displaystyle o(n^2) > nlogn \) e di conseguenza tenderebbe a +infinito per x-> + infinito.
Ma con l'O-grande?
Spero di non essere stato troppo confuso!
Risposte
Ma lì fai un esempio numerico, non c'è un modo per capirlo qualitativamente? cioè che "ad occhio" posso intuire a cosa tende?
Semplicemente non è vera sempre, ti basta un controesempio. Ovviamente in alcuni casi (per alcuni $O(n^2)$) è vera.
Ti basta prendere $n^2=O(n^2)$, che è vero perchè banalmente $n^2<=Cn^2$ con $C=1$, e notare che
$lim_(n->+oo) 1+ n^2/(n logn) = +oo$, quindi le tue due successioni non sono asintotiche.
Ti basta prendere $n^2=O(n^2)$, che è vero perchè banalmente $n^2<=Cn^2$ con $C=1$, e notare che
$lim_(n->+oo) 1+ n^2/(n logn) = +oo$, quindi le tue due successioni non sono asintotiche.
Capito, quindi per verificarla alla fine mi basta prendere un numero che sta dentro O-grande, sostituirlo ad esso nell'equazione e verificare a cosa tende, giusto? (ma C non viene messa da nessuna parte o mi sono perso io qualcosa?)
Lo stesso procedimento posso applicarlo anche per Theta grande e Omega?
Lo stesso procedimento posso applicarlo anche per Theta grande e Omega?
"Snakethesniper":
Capito, quindi per verificarla alla fine mi basta prendere un numero che sta dentro O-grande
Beh un numero direi proprio di no, caso mai una successione.
"Snakethesniper":
ma C non viene messa da nessuna parte o mi sono perso io qualcosa?
Non ho capito cosa vuoi dire.
"Snakethesniper":
Lo stesso procedimento posso applicarlo anche per Theta grande e Omega?
Se me li definisci magari ti posso rispondere, non le conosco a memoria tutte.
Per la C intendo che se mi trovo in una situazione in cui \(\displaystyle an <= C|bn| \) con C per esempio uguale a 3, quando poi inserisco la successione all'interno dell'equazione, quel 3 viene inserito anch'esso?
Cioè nell'esempio di prima era C=1, quindi anche inserendolo non si "vedrebbe", ma se fosse diverso da 1 andrebbe inserito da qualche parte oppure no? Mettiamo che era \(\displaystyle <=Cn^2 \) con C=3 appunto, rimaneva sempre \(\displaystyle n^2/nlogn \) oppure qualcosa tipo \(\displaystyle 3n^2/nlogn \)?
Altra curiosità, nell'esempio che hai fatto non bastava prendere \(\displaystyle n=O(n^2) \)? In quanto \(\displaystyle n<=Cn^2 \) con C=1 ?
Cioè nell'esempio di prima era C=1, quindi anche inserendolo non si "vedrebbe", ma se fosse diverso da 1 andrebbe inserito da qualche parte oppure no? Mettiamo che era \(\displaystyle <=Cn^2 \) con C=3 appunto, rimaneva sempre \(\displaystyle n^2/nlogn \) oppure qualcosa tipo \(\displaystyle 3n^2/nlogn \)?
Altra curiosità, nell'esempio che hai fatto non bastava prendere \(\displaystyle n=O(n^2) \)? In quanto \(\displaystyle n<=Cn^2 \) con C=1 ?
Non ha senso dire che non si vedrebbe.. spero il tuo problema non sia questo: $1*a=a$.
Comunque non bastava prendere $n$ perchè in quel caso avresti avuto $nlogn+n$ che è asintotico a $nlogn$..
Comunque non bastava prendere $n$ perchè in quel caso avresti avuto $nlogn+n$ che è asintotico a $nlogn$..
Quello che voglio dire io è, una volta che trovo la costante C che rende vero \(\displaystyle an <= C|bn| \), nel momento in cui nell'equazione come nel caso di prima vado a sostituire l'O-grande, devo inserire questa costante C?
Tipo nel \(\displaystyle n^2/nlogn \) c'è stato un \(\displaystyle 1*n^2/nlogn -> n^2/nlogn \) oppure metto solo an senza la costante?
Tipo nel \(\displaystyle n^2/nlogn \) c'è stato un \(\displaystyle 1*n^2/nlogn -> n^2/nlogn \) oppure metto solo an senza la costante?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo