Hai mai scritto un pezzo di codice che vola quando lo testi con dieci righe di dati, per poi bloccarsi irrimediabilmente non appena gliene dai in pasto diecimila? Quella sensazione frustrante non è un caso, ma una questione di crescita. Capire la notazione asintotica ([math]O[/math], [math]\Omega[/math], [math]\Theta[/math]) non è solo un esercizio accademico per superare un esame. È il superpotere che ti permette di prevedere il comportamento del tuo software su larga scala.
In informatica il calcolo asintotico è utilizzato per analizzare la complessità di un algoritmo. Parlando di complessità di un algoritmo, bisogna specificare che il tempo T(n) e lo spazio S(n) dipendono dalle dimensioni dell'input n (ad esempio, se un array è l'input principale, n sarà la lunghezza di tale array). Per poter definire univocamente S(n) e T(n) bisogna distinguere il caso peggiore, caso migliore e caso medio. Si distingue, per ogni n, l'input che genera il tempo e lo spazio maggiore (caso peggiore) e l'input che genera il tempo e lo spazio minore (caso migliore); inoltre si considera una media di tutti i casi possibili (caso medio) a parità di n.
Le Basi della Notazione Asintotica
La notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni. Il suo obiettivo è quello di caratterizzare il comportamento di una funzione per argomenti elevati in modo semplice, ma rigoroso, al fine di poter confrontare il comportamento di più funzioni fra loro. Questa notazione è stata introdotta per la prima volta dal teorico dei numeri tedesco Paul Bachmann nel 1894[1], nel secondo volume del libro Analytische Zahlentheorie ("Teoria analitica dei numeri"), il cui primo volume (che ancora non conteneva la notazione O-grande) uscì nel 1892. La notazione divenne popolare grazie al lavoro di un altro teorico dei numeri tedesco, Edmund Landau[2], ragione per cui oggi è alcune volte chiamata simbolo di Landau.
Si tratta di notazioni matematiche che servono ad indicare (rispettivamente) il limite superiore, inferiore e stretto della complessità temporale asintotica di un algoritmo. Non è che devi "scegliere". Per ogni algoritmo con relativa complessità, è possibile definire un limite superiore e inferiore e, nel caso questi coincidano, un limite stretto.
Notazione O-grande (Big O)
In *pratica*, sì. Dire che la complessità di un algoritmo sia O(f(n)), dove f(n) è una generica funzione in n (come proprio n o n^2 o nlogn) significa che essa non crescerà mai "più rapidamente" di f(n), quindi appunto che l'algoritmo ha un tempo di esecuzione che è al massimo proporzionale a f(n) (quindi nel caso peggiore).
La notazione O-grande risulta utile nell'analisi dell'efficienza degli algoritmi. Inoltre, anche i coefficienti diventano irrilevanti se compariamo l'espressione precedente ad una di ordine superiore, come una contenente un termine n³ oppure 2n. La notazione O-grande può anche essere usata per descrivere il termine di errore in una approssimazione di una funzione.
Si supponga che e siano due funzioni definite su qualche sottoinsieme dei numeri reali[3]. Nella matematica, i comportamenti asintotici tendenti a e ad sono entrambi considerati. Supponiamo . Osserviamo che per valgono le disuguaglianze e . L'affermazione " è dell'ordine di " è spesso scritta come "". Questo è un abuso di notazione: non stiamo realmente affermando l'uguaglianza fra due funzioni, in quanto non rappresenta una singola funzione ma una classe di funzioni. A volte si scrive anche "" per indicare che . Anche questo è un abuso di notazione: quella indicata nella prima espressione non è una vera uguaglianza, in quanto non è simmetrica.
Notazione Omega-grande (Ω)
La notazione asintotica Omega ([math]\Omega[/math]) definisce un limite inferiore asintotico. Indica che la complessità di un algoritmo non sarà mai inferiore a una certa funzione, anche nel caso migliore.
Notazione Theta-grande (Θ)
La notazione asintotica Theta ([math]\Theta[/math]) definisce un limite asintotico stretto. Indica che la complessità di un algoritmo è limitata sia superiormente che inferiormente dalla stessa funzione. Se una funzione è [math]\Theta[/math](g(n)) allora è anche O(g(n)) e [math]\Omega[/math](g(n)) perché esiste sia un limite asintotico superiore che inferiore.
Gerarchie di Complessità: Cosa Significa Davvero?
Questi confronti stabiliscono una vera e propria “gerarchia del potere computazionale”. Confrontiamo le funzioni a coppie usando limiti e proprietà asintotiche note. Questa è una domanda fondamentale che tocca il cuore della gerarchia asintotica.
Logaritmi e Polinomi
L’approccio algebrico evidenzia un fatto fondamentale: tutti i logaritmi in basi diverse sono equivalenti asintoticamente a meno di un fattore costante. Questo esercizio dimostra una verità cruciale: nel mondo asintotico, tutte le basi dei logaritmi sono parenti stretti. Quando un algoritmo ha una complessità logaritmica, come la ricerca binaria (O(log n)), non ha quasi nessuna importanza se la base del logaritmo è 2, 10 o e. Applicazione Concreta: Un programmatore che ottimizza una ricerca in un albero binario (base 2) o in un B-Albero (che può avere una base molto più alta) sa che entrambi offrono prestazioni logaritmiche. La scelta tra le due strutture non dipenderà dalla “velocità” del logaritmo, ma da altri fattori come l’uso della memoria cache e l’accesso al disco.
Ad esempio, anche se [math]\ln{n}[/math] cresce lentamente, esso supererà [math]100[/math] quando [math]n > e^{100}[/math]. Da quel punto in poi, la funzione [math]n^{\ln{n}}[/math] cresce più velocemente di [math]n^{100}[/math].
Poiché [math]0 < \frac{2}{3} < 1[/math], il termine esponenziale [math]\left(\frac{2}{3}\right)^n[/math] tende a [math]0[/math] molto più rapidamente di quanto il termine [math]n[/math] tenda a infinito.
Funzioni Super-polinomiali e Sub-esponenziali
È una funzione super-polinomiale ma sub-esponenziale. La notazione asintotica [math]\Omega[/math] è fondamentale per distinguere queste categorie.
Funzioni Esponenziali e Fattoriali
Esponenziali Miste (n * 2^n vs 3^n): Qui la lezione è brutale. Immagina di avere due approcci per risolvere un problema (es. un problema di ottimizzazione). Il primo richiede di testare n configurazioni per 2^n possibilità (n * 2^n), mentre il secondo ne testa 3^n. Per valori piccoli di n il primo potrebbe sembrare peggiore, ma asintoticamente l’algoritmo 3^n esploderà molto più velocemente. La base dell’esponenziale è il fattore dominante, il vero killer delle prestazioni. Una funzione esponenziale con base maggiore batte qualsiasi funzione polinomiale moltiplicata per un’esponenziale con base minore (come visto nel Caso 3).
L’apocalisse computazionale. Legata a problemi di permutazione (es. risolvere un puzzle provando ogni combinazione). Diventa ingestibile per n incredibilmente piccoli (già 20!).
Applicazioni Concrete e Implicazioni
L’analisi asintotica può sembrare astratta, ma questi esercizi sono tutt’altro che teorici. Ciascuno di essi nasconde una lezione fondamentale per chi progetta software e sistemi.
Perché sono interessanti? Questi confronti stabiliscono una vera e propria “gerarchia del potere computazionale”. Applicazione Concreta: Un algoritmo con complessità O(√n) potrebbe essere accettabile per un set di dati di un miliardo di elementi, mentre uno O((ln n)¹⁰) sarebbe quasi istantaneo.
Perché è interessante? Questo esercizio dimostra una verità cruciale: nel mondo asintotico, tutte le basi dei logaritmi sono parenti stretti.
Perché sono interessanti? Questi confronti stabiliscono una vera e propria “gerarchia del potere computazionale”.
Perché è interessante? f₁(n) = (ln n)¹⁰⁰: Polilogaritmica. Velocissima. f₂(n) = n⁰.⁰⁰¹: Polinomiale. L’universo dei problemi “trattabili”. f₃(n) = n^(ln n): Super-polinomiale. Questa è la terra di mezzo. Più lenta di qualsiasi polinomio, ma più veloce di un vero esponenziale. È una funzione “quasi-esponenziale” che appare in alcuni algoritmi di fattorizzazione o in contesti crittografici. f₄(n) = 1.001ⁿ: Esponenziale. La soglia dei problemi “intrattabili”. f₅(n) = n!: Fattoriale. L’apocalisse computazionale. Legata a problemi di permutazione (es. risolvere un puzzle provando ogni combinazione). Diventa ingestibile per n incredibilmente piccoli (già 20!).
Lezione 09 Notazione asintotica
Le tavole hash sono strutture dati impiegate per implementare dizionari, cioè strutture che consentono solo le operazioni di inserimento, cancellazione e ricerca. Le operazioni di inserimento e cancellazione introducono una caterva di problemi: come trovare una funzione hash decente che possa evitare le collisioni quanto più possibile, cercando cioè di distribuire gli elementi in maniera quanto più uniforme possibile tra le varie entry? E, in caso di collisioni, come gestirle?
Nel caso migliore (che come vedremo, corrisponde all'array già ordinato) è , quindi anche . Sapendo che esiste un algoritmo (ad esempio il Quick Sort) che risolve il problema dell'ordinamento in un tempo possiamo facilmente dire che il limite superiore dell'ordinamento è . A questo punto si presenta un gap: il limite superiore è diverso da quello inferiore per un ordine di infinito ( cresce più di ).
Inoltre, anche i coefficienti diventano irrilevanti se compariamo l'espressione precedente ad una di ordine superiore, come una contenente un termine n³ oppure 2n.
Il risultato emerge immediatamente: il rapporto è costante!
La base dell’esponenziale è il fattore dominante, il vero killer delle prestazioni.
tags: #notazione #asintotica #omega