Complessità degli algoritmi
Ogni algoritmo ha la sua complessità, che può essere espressa in notazione matematica. Questa panoramica mostra la complessità tipica degli algoritmi in base alla dimensione dei dati di input (cioè il numero di elementi con cui lavorano) e quali tipi di algoritmi sono adatti a quale tipo di compito.
In generale, c'è un algoritmo specializzato migliore per ogni tipo di problema. Nessun algoritmo è universalmente migliore, e bisogna sempre conoscere il proprio contesto.
Notazione Big O
La Notazione Big O è usata per classificare gli algoritmi in base a come il loro tempo di esecuzione o i requisiti di memoria aumentano con l'aumentare delle dimensioni dell'input.
Il seguente grafico mostra gli ordini di crescita più comuni degli algoritmi specificati in Big O Notation.
Di seguito è riportato un elenco di alcune delle notazioni Big O più comunemente usate e un confronto delle loro prestazioni rispetto alle diverse dimensioni dei dati di input.
| Notazione Big O | Complessità per 10 elementi | Complessità per 100 elementi | Complessità per 1000 elementi |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log N) | 3 | 6 | 9 |
| 10 | 100 | 1000 | |
| O(N log N) | 30 | 600 | 9000 |
| O(N^2) | 100 | 10000 | 1000000 |
| O(2^N) | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 |
Complessità delle operazioni sulla struttura dei dati
| Struttura di dati | Accesso | Ricerca | Inserisci | Rimuovi | Commenta |
|---|---|---|---|---|---|
| 1. n, n, n, n, n, n, n, n, n. | |||||
| Stack | n | n | n | 1 | 1 |
| Coda | n | n | n | 1 | |
| Lista collegata | n | n | n | 1 | n |
| Nel caso di una funzione hash perfetta, la complessità sarà O(1) | |||||
| Albero di ricerca binario | n | n | n | n | Nel caso di un albero bilanciato, la complessità sarà O(log(n)). |
| B-Tree | log(n) | log(n) | log(n) | log(n) | log(n) |
| Albero Rosso-Nero | log(n) | log(n) | log(n) | log(n) | |
| AlberoAVL | log(n) | log(n) | log(n) | log(n) | log(n) |
| Quando si cercano i "falsi positivi". |
Complessità degli algoritmi di ordinamento
| Nome dell'algoritmo | Migliore | Media | Peggiore | Memoria | Stabile? | Commento |
|---|---|---|---|---|---|---|
| Bubble sort | n | n2 | n2 | 1 | Sì | |
| Insertion sort | n | n2 | n2 | 1 | ||
| Selection sort | n2 | n2 | n2 | 1 | ||
| Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |
| Merge sort | n log(n) | n log(n) | n log(n) | n | Sì | |
| Quick sort | n log(n) | n log(n) | n2 | log(n) | No | |
| Shell sort | n log(n) | dipende dalla sequenza | n (log(n))2 | 1 | No | |
| Counting sort | n + r | n + r | n + r | n + r | Sì | r - il numero più grande nella matrice |
| Radix sort | n * k | n * k | n * k | n + k | Sì | k - lunghezza della chiave più lunga |
Jan Barášek Maggiori informazioni su l'autore
L'autore lavora come sviluppatore senior e architetto software a Praga. Progetta e gestisce grandi applicazioni web che conoscete e usate. Dal 2009 ha acquisito una grande esperienza che trasmette attraverso questo sito web.
Sarò felice di aiutare:
Contact