 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
aiuto su espressioni asintotiche
Clicca QUI per vedere il messaggio nel forum |
| Larios |
Ciao,
qualcuno sarebbe cosi gentile da dirmi come dimostrare che:
7n^2 + n log n = O (n^3)
pensavo fosse O(n^2) ma è sbagliato :?
Grazie |
| Larios |
Originally posted by Larios
7n^2 log n + n log n = O (n^3)
e questo quello corretto scusate |
| mauri |
| nn è sbagliato ke sia O(n^2)...mmmm....anke io avrei dato la tua stessa soluzione...cmq..ti posso kiedere dv hai trovato gli esercizi? |
| Larios |
sono sull'eserciziario di algoritmi del diurno e la risposta O(n^2) sarebbe stata sbagliata(basta risolvere 7n^2 log n + n log n <= c *(n^3)) e riesco a dimostrare che è cosi, ma non riesco a mia volta dimostare e ottenere come risultato O(n^3)
E' per via dei logaritmi che stanno li che sale piu di O(n^2), ma non lo so dimostare :) |
| DarkSchneider |
da quel poco che so O definisce un limite superiore, quindi che la suddetta espressione sia O(n^3) mi sembra corretto,
è un limite superiore non stretto |
| Larios |
questo è come l'ho svolto io:
7n^2 log n+n logn
riporto i vari passaggi per trovare O grande
n^2 logn+((n logn) /7)
((n logn) / 7)<n2logn per n > 1
riscrivo
n^2 logn+((n logn)/7)<2⋅(n^2 logn) ---> secondo me 2⋅(n^2 logn) non va bene...
ottengo cosi in fine rimoltiplicando per 7
7n^2 logn+ (n logn)<14 n^2 logn
teoricamente sarebbe O(n^2 logn) con un c di 14
vi fa venire in mente qualcosa oppure capite cosa c'è di sbagliato? |
| mauri |
ma è fatto bn l'eserciziario???cioè kn tnt di spiegazioni???
grazie anticipatamente ;);););) |
| Bloom |
Secondo me è cosi ma nn sono sicura dell'ultimo passaggio.
7n^2logn+nlogn=0
per n>=1
logn^(7n^2)+logn^n=0 per la proprieta nloga=log a^n
logn^(7n^3)=0 per la proprietà log(ab)=loga+logb
quindi
7n^3=n^0
7n^3=1
n^3=1/7
n^3-1/7=0
insomma l'ordine di grandezza è O (n^3)
Almeno penso che sia cosi.
Che ne pensate? |
| Larios |
si credo proprio che sia corretto...
ma non ho capito pero come si passa da logn^(7n^3)=0 a 7n^3=n^0 |
| Bloom |
Proprità dei logaritmi...
elevo entrambi i membri a n.
Cosi il primo membro a sinistra si semplifica (algoritmo e esponenziale
sono due operazioni opposte).
Se lo faccio al primo membro la stessa cosa devo farlo al secondo per mantenere l'uguaglianza
Sono stata chiara? |
| Larios |
| si mi ero dimenticato di quella proprieta, grazie :) |
| Bloom |
di nulla...:-)
Se fossero solo questi i problemi
Io sto litigando con i colori del progetto daltonismo..
Tremo al progetto di gennaio.
Devo capire come verificare esistenza un determinato percorso su un grafo.
Ciao! |
|
|
|
|
