Calcolatore di crescita Big-O
Dati di input
| Dimensione di input n | 20 |
|---|
Calcolatore di crescita Big-O
Inserisci una dimensione di input n per confrontare quante operazioni richiede ciascuna classe di complessità temporale comune — da O(log n) a O(n!).
Dati di input
Dimensione di input
Risultati
Inserisci un valore per visualizzare i risultati.
Complessità comuni
Crescita estrema
Crescita Big-O
La notazione Big-O classifica come la domanda di risorse di un algoritmo scala con la dimensione dell'input. Invece di misurare i secondi su una macchina specifica, cattura la forma della crescita — il lavoro raddoppia quando n raddoppia, o quadruplica? Le sei complessità seguenti sono quelle che si incontrano più spesso nei libri di testo e nei colloqui tecnici.
Le sei classi comuni
O(log n) — Logaritmica. Ogni passo elimina una frazione costante del lavoro rimanente. La ricerca binaria su un array ordinato di un miliardo di elementi richiede solo 30 confronti perché dimezza lo spazio di ricerca a ogni passo. Le operazioni di lookup su BST bilanciati e molte ricorrenze divide-et-impera rientrano in questa categoria.
O(n) — Lineare. Il lavoro cresce in proporzione diretta alla dimensione dell'input. Scansionare un array una volta per trovarne il massimo, contare i caratteri in una stringa o leggere ogni elemento da una lista sono operazioni lineari. Gli algoritmi lineari sono generalmente considerati efficienti.
O(n log n) — Linearitmica. La complessità più comune per l'ordinamento. Merge sort, heapsort e Timsort (usato in Python e Java) raggiungono tutti O(n log n), che è anche il limite inferiore teorico per l'ordinamento basato su confronti. Con , si tratta di circa venti milioni di operazioni — rapido in pratica.
O(n²) — Quadratica. Due cicli annidati sull'input. Bubble sort, insertion sort e la moltiplicazione naïve tra matrici hanno tutti complessità O(n²) nel caso peggiore. Con si hanno cento milioni di operazioni; con si arriva a un bilione — impraticabile per dati di grandi dimensioni.
O(2ⁿ) — Esponenziale. Il lavoro raddoppia per ogni elemento aggiuntivo. L'algoritmo ricorsivo naïve di Fibonacci ricalcola i sottoproblemi in modo esponenziale; l'enumerazione bruta di tutti i sottoinsiemi di un insieme cresce anch'essa come . Con n = 40 il conteggio supera un bilione.
O(n!) — Fattoriale. La classe a crescita più rapida nell'analisi algoritmica quotidiana. Le soluzioni brute force ai problemi di permutazione — elencare ogni possibile tour nel Problema del Commesso Viaggiatore — eseguono un'operazione per permutazione, e ci sono permutazioni in totale. Con n = 20, il conteggio supera i due trilioni di operazioni.
Esempio con n = 20
Il rapporto tra O(n log n) e O(n!) con n = 20 è circa — la differenza tra un ordinamento rapido e un'attesa superiore all'età dell'universo.
Guida pratica
Le costanti e gli effetti della cache contano per n piccoli; la complessità domina per n grandi. Una soglia di circa n = 10.000 è quella a partire dalla quale O(n²) diventa scomodo su hardware moderno (assumendo operazioni semplici). Oltre n = 10^6 serve generalmente un algoritmo O(n log n) o migliore. Gli algoritmi esponenziali e fattoriali richiedono approssimazioni, programmazione dinamica o strategie di potatura per qualsiasi input reale.
Domande frequenti (FAQ)
Cosa misura effettivamente la notazione Big-O?
La notazione Big-O descrive il limite superiore di come il tempo di esecuzione (o l'utilizzo di memoria) di un algoritmo cresce all'aumentare della dimensione di input n. Ignora deliberatamente i fattori costanti e i termini di ordine inferiore perché diventano meno rilevanti al crescere di n.
Un algoritmo O(n²) supererà sempre un algoritmo O(n log n) per input sufficientemente grandi, indipendentemente dalla velocità dell'hardware. Big-O è uno strumento per confrontare i design degli algoritmi — non una previsione precisa del tempo di esecuzione reale.
Perché il logaritmo è in base 2?
La maggior parte degli algoritmi divide-et-impera (ricerca binaria, merge sort, BST bilanciati) divide il lavoro a metà a ogni passo, quindi la profondità di tale divisione è log₂ n. Nell'analisi Big-O la base del logaritmo è solo un fattore costante e non cambia la classe di complessità — log₂ n e log₁₀ n differiscono solo per una costante.
Ma la base 2 è convenzionale in informatica a causa della suddivisione binaria. Questo calcolatore utilizza la base 2 per rispettare tale convenzione.
A quale dimensione di input la complessità inizia a contare?
Per input piccoli, ad esempio n < 50, un algoritmo O(n²) ben ottimizzato supera spesso uno O(n log n) teoricamente più veloce perché ha un overhead costante inferiore e un comportamento migliore con la cache. La complessità inizia a dominare quando n raggiunge le centinaia o le migliaia.
Con n = 1.000, un ordinamento O(n log n) esegue circa 10.000 confronti mentre uno O(n²) ne esegue 1.000.000. Con n = 1.000.000 il divario è tra un miliardo e un bilione — la complessità è diventata l'unico fattore rilevante.
O(n!) è mai usato in pratica?
Gli algoritmi O(n!) sono impraticabili per tutti gli input tranne quelli più piccoli. Con n = 20, n! supera i due trilioni di operazioni — ben oltre ciò che qualsiasi computer può completare nel corso di una vita umana.
In pratica, i problemi NP-difficili come il Problema del Commesso Viaggiatore vengono risolti con algoritmi di approssimazione, euristiche o programmazione dinamica che evitano di enumerare tutte le permutazioni. La colonna fattoriale in questo calcolatore serve a ricordare perché esistono quelle tecniche di approssimazione.