Complessità degli algoritmi

📅   03. 08. 2021
👤   Jan Barášek

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
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
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 r - il numero più grande nella matrice
Radix sort n * k n * k n * k n + k 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