 | |
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 |
[HELP] Complessità di 1 algoritmo
Clicca QUI per vedere il messaggio nel forum |
| antares85 |
| Ciao ragazzi,fra 2 settimane c'è l'esame e non ho ancora capito come cavolo si calcola la complessità di un algoritmo (O grande,o piccolo,notazione asintotica,ecc) ma sono l'unico pirla che non li capisce? Qualcuno può darmi delucidazioni o postare degli appunti relativi per cortesia? |
| antares85 |
| Ovviamente anche riguardo costo logaritmico e uniforme...Grazie!!! |
| kingoff |
allora.
devi interpretare i vari Ogrande opiccolo, omega ecc.
Ovvero quando li incontri li sostituisci con parole italiane:
f e g sono funzioni
f=Ogrande(g) = f cresce al più come g
f=opiccolo(g) = f cresce meno di g
f=OMEGAgrande(g) = f cresce almeno come g
f=omegapiccolo(g) = f cresce più di g
f=THETA(g) = f cresce circa come g |
| antares85 |
ti ringrazio per la spiegazione,ma credo che il mio problema sia il fatto di nn sapere come si fa a capire se una funzione cresce piu' o meno di un'altra,probabilmente mi mancano le basi matematiche.
Non sapendo queste cose è cmq possibile calcolare il criterio di costo logaritmico e uniforme o sono spacciato? |
| kingoff |
beh non è difficile...lg n è asintoticamente minore di n che lo è di n^2 che lo è di n^n....
ovvero se tu ti trovi a dover scegliere quale è asintoticamente magigore tra n*100000 e n^2 scegli n^2
Questo perchè quando n è molto grande (diciamo 100 000 000 000 000 000) le operazioni li sopra danno due risultati molto distanti...
Il trucco sta nell'individuare in una funzione qual'è l'elemento dominante,(NON 1000000 in questo caso,anche se fa un po di scena perchè è lineare)
per il resto...buona fortuna...ne abbiamo tutti bisogno... |
|
|
|
|
