ordine grandezza vs O grande
Clicca QUI per vedere il messaggio nel forum |
| Kira82 |
So che ci sono molti thread che ne parlano ma non sapevo dove metterlo quindi ne creo uno nuovo...
Qualcuno di voi mi può per favore spiegare come valutare ordine di grandezza e O grande?
So che f(n)=ordine grandezza(g(n)) significa che Ag(n)<=f(n)<=B(g(n)) e invece f(n)=O(g(n)) significa che f(n)<=Cg(n) ma non riesco a comprendere alcune cose.
Ad esempio qual è l'O e l'ordine di grandezza di O(nlogn)*1/logn?
e di nlogn+3n^2?
e di 5n+n^2?
Sulle dispense c'è poi 5n^2+n che è sia ordine di grandezza che O di n^2, invece 3n^4 è O(n^5) ma perchè? e quest'ultimo sarebbe ordine di grandezza di..?
Aiutoooooooo..
Grazie mille |
| ideafix |
O è un limite superiore
per cui 3n^4 è O(n^4) ma anche O(n^5)......O(n^100)..
il discorso fatto in maniera un po semplificata è se hai un polinomio l'ordine di grandezza è quello della potenza superiore.
Costanti additive e moltiplicative non contano.
per cui
nlogn +3n^2 è 0(n^2) |
| Larios |
O(nlogn)*1/logn
l'ordine di grandezza è O(n) perchè O(nlogn) è come dire per esempio 6nlogn, quindi viene 6nlogn *1/logn= 6n = O(n)
3n^4 = O(n^4) questo è il limite superiore stretto,
la regola generale che devi usare è questa f(n) <= c * g(n) che hai scritto (cioè trovare un c tale che sia verificata)
3n^4 =< c * n^4
se ti racci i grafici ti viene molto piu facile capire il tutto a mio parere
ovviamente come diceva ideafix è vero anche O(n^100) |
| Kira82 |
Grazie tante..credo di iniziare a capire..invece l'ordine di grandezza(intendo Theta) per O(n)? e di 3n^4? Perchè mi viene da ragionare nello stesso modo in quanto A*n^4<=3n^4<=B*n^4, ma così significherebbe che O implica ordine di grandezza, invece non è vero..quindi potete darmi una delucidazione sull'ordine di grandezza come avete fatto sull'O?
Grazie ancora..mi state salvando.. |
|
|
|
