Estratto del documento
Classificazione degli algoritmi
Prestazioni degli algoritmi
Un algoritmo può essere classificato in funzione delle proprie prestazioni:
- Efficiente: Un algoritmo è considerato efficiente se il suo tempo di esecuzione (caso peggiore) è polinomiale.
- Inefficiente: Un algoritmo è considerato inefficiente se il suo tempo di esecuzione (caso peggiore) è almeno esponenziale.
Complessità dei problemi algoritmici
Un problema algoritmico può essere classificato in funzione della propria complessità, ovvero le prestazioni del più veloce algoritmo che lo risolve:
- Trattabile: Un problema è considerato trattabile se la sua complessità è al più polinomiale.
- Non trattabile: Un problema è considerato non trattabile se la sua complessità è almeno esponenziale.
Ipotetico tempo di esecuzione
Ipotesi: una istruzione di Java viene eseguita in 10 s.
Confronto delle prestazioni tra alcuni algoritmi di ordinamento
| Algoritmo | Caso migliore | Caso medio | Caso peggiore |
|---|---|---|---|
| Merge sort | n(log (n)) | n(log (n)) | n(log (n)) |
| Selection sort | n2 | n2 | n2 |
| Insertion sort | n | n2 | n2 |
Se si sa che l'array è “quasi” ordinato, è meglio usare l'ordinamento per inserimento. Esempio notevole: un array che viene mantenuto ordinato per effettuare ricerche, inserendo ogni tanto un nuovo elemento e poi riordinandolo.
Anteprima
Vedrai una selezione di 1 pagina su 1
Dettagli
SSD
Scienze matematiche e informatiche
INF/01 Informatica
I contenuti di questa pagina costituiscono rielaborazioni personali del
Publisher enricopava di informazioni
apprese con la frequenza delle lezioni
di Informatica 1 e studio autonomo di eventuali libri di riferimento in preparazione
dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale
dell'università Università degli Studi di Padova o del prof Avanzini Federico.
Recensioni
3 Dicembre 2022
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
Appunto