L’efficienza di un algoritmo dipende da due parametri:
- Complessità temporale
- Complessità spaziale
Complessità temporale:
La complessità temporale è definita come il numero di volte in cui un particolare set di istruzioni viene eseguito anziché il tempo totale impiegato. Questo perché il tempo totale impiegato dipende anche da alcuni fattori esterni come il compilatore utilizzato, la velocità del processore, ecc.
Complessità spaziale:
La complessità spaziale è lo spazio di memoria totale richiesto dal programma per la sua esecuzione.
Entrambi sono calcolati in funzione della dimensione dell'input (n). Una cosa importante qui è che, nonostante questi parametri, l'efficienza di un algoritmo dipende anche da loro natura E taglia di IL ingresso.
Tipi di complessità temporale:
- Miglior complessità temporale: Definire l'input per il quale l'algoritmo impiega meno tempo o tempo minimo. Nel migliore dei casi calcola il limite inferiore di un algoritmo. Esempio: nella ricerca lineare, quando i dati di ricerca sono presenti nella prima posizione di dati di grandi dimensioni, si verifica il caso migliore.
- Complessità temporale media: Nel caso medio, prendi tutti gli input casuali e calcola il tempo di calcolo per tutti gli input.
E poi lo dividiamo per il numero totale di input. - Peggiore complessità temporale: Definire l'input per il quale l'algoritmo richiede molto tempo o tempo massimo. Nel peggiore dei casi calcolare il limite superiore di un algoritmo. Esempio: nella ricerca lineare, quando i dati di ricerca sono presenti nell'ultima posizione di dati di grandi dimensioni, si verifica il caso peggiore.
Di seguito è riportato un rapido foglio di revisione a cui è possibile fare riferimento all'ultimo minuto:
| Algoritmo | Complessità temporale | Complessità spaziale | ||
|---|---|---|---|---|
| Migliore | Media | Peggio | Peggio | |
| Ordinamento selezione | SU2) | SU2) | SU2) | O(1) |
| Ordinamento a bolle | SU) | SU2) | SU2) | O(1) |
| Ordinamento per inserimento | SU) | SU2) | SU2) | O(1) |
| Ordinamento heap | O(n log(n)) | O(n log(n)) | O(nlog(n)) | O(1) |
| Ordinamento rapido | O(n log(n)) | O(n log(n)) | SU2) | SU) |
| Unisci ordinamento | O(n log(n)) | O(n log(n)) | O(n log(n)) | SU) |
| Ordinamento del secchio | O(n+k) | O(n+k) | SU2) | SU) |
| Ordina radice | OK(nk) | OK(nk) | OK(nk) | O(n+k) |
| Conteggio | O(n+k) | O(n+k) | O(n+k) | Freccia) |
| Ordinamento della shell | O(n log(n)) | O(n log(n)) | SU2) | O(1) |
| Tim Ordina | SU) | O(nlog(n)) | O(nlog(n)) | SU) |
| Ordinamento dell'albero | O(n log(n)) | O(n log(n)) | SU2) | SU) |
| Ordinamento del cubo | SU) | O(n log(n)) | O(n log(n)) | SU) |
Vedi anche:
- Ricerca e ordinamento di articoli
- Domande GATE dell'anno precedente sull'ordinamento
- Complessità temporale e spaziale dell'ordinamento di inserimento
- Complessità temporale e spaziale dell'ordinamento della selezione
- Complessità temporale e spaziale del Bubble Sort
- Complessità temporale e spaziale dell'ordinamento rapido
- Complessità temporale e spaziale del Merge Sort
- Complessità temporale e spaziale dell'algoritmo Radix Sort