Lezione 3 - Notazioni asintotiche

Le Notazioni Asintotiche e l’Analisi della Complessità degli Algoritmi

Concetti preliminari di analisi asintotica

Confronto tra le principali funzioni di crescita

Quando si analizza l’efficienza di un algoritmo, non ci si limita a misurare il tempo effettivo di esecuzione sul computer, poiché tale misura dipende da fattori cangianti da macchina a macchina, quello che si punta a fare è descrivere in modo astratto e generale il comportamento dell’algoritmo, indipendentemente dal contesto. In particolare si studia come il tempo di esecuzione cresce al crescere della dimensione dell’input $n$.

• $T(n)$ rappresenta la funzione di costo dell’algoritmo. Un algoritmo è fatto di vari passi, un passo può essere considerato come un’operazione di base che richiede un tempo costante.

Diremo che due algoritmi sono più o meno efficienti a seconda di come cresce la loro funzione $T(n)$: un algoritmo la cui funzione di costo cresce più lentamente sarà, per input sufficientemente grandi, più efficiente di uno con crescita più rapida.

Dalla necessità di classificare i vari algoritmi nascono le notazioni asintotiche, che ci permettono per l’appunto di rappresentare questa idea di crescita trascurando i dettagli che non influiscono sul comportamento generale dell’algoritmo.

Confronto tra le principali funzioni di crescita

Alcune funzioni crescono lentamente, altre molto rapidamente. Immaginiamo di avere diversi algoritmi che risolvono lo stesso problema, ma con funzioni di costo differente:

• uno è proporzionale a $a\log n$
• un altro a $n$
• un altro ancora a $n^2$ Per valori piccoli di $n$ le differenze possono sembrare trascurabili, ma per input abbastanza grandi la situazione cambia, ad esempio con $n=1000$: ${\log }_{2}n\approx 10,n=1000,n^2=10^6,2^n\approx 10^{301}$ In generale abbiamo diversi tipi di crescita:

1. Funzioni costanti $T(n)=1$ rappresentano algoritmi che impiegano sempre lo stesso numero di operazioni indipendentemente da $n$
   • Accesso ad un elemento di un array
2. Funzioni logaritmiche $T(n)=\log n$ descrivono algoritmi che riducono il problema di un fattore costante a ogni passo
   • Ricerca binaria
3. Funzioni lineari $T(n)=n$ corrispondono ad algoritmi che analizzano tutti gli elementi dell’input una sola volta
   • Scansione di un array
4. Funzioni linearitmiche $T(n)=n\log n$ caratterizzano algoritmi efficienti di ordinamento
   • Merge sort e Heap sort
5. Funzioni polinomiali $T(n)=n^k$ includono molti algoritmi praticabili ma diventano rapidamente onerose per $k>2$
   • Bubble sort
6. Funzioni esponenziali e fattoriali: descrivono problemi di natura combinatoria per i quali il numero di soluzioni cresce esplosivamente con $n$
   • Calcolo di tutte le permutazioni Sono elencate in ordine di crescita crescente: una funzione situata più in basso cresce più rapidamente di tutte quelle sopra di essa

Termini e fattori dominanti e trascurabili

Quando si analizza il tempo di esecuzione di un algoritmo la funzione di costo $T(n)$ può contenere più termini, si chiama termine dominante quello che determina l’andamento complessivo della funzione per valori grandi di $n$, quando abbiamo più termini quello che dobbiamo fare è:

• Eliminare i termini di ordine inferiore, cioè quelli che crescono più lentamente
• Si ignorano i fattori costanti che moltiplicano i termini
• Si conserva solo il termine che domina Di seguito degli esempi:

1. $T(n)=3n^2+5n+10$ in questa funzione domina il $3n^2$ ed essendo $3$ un coefficiente moltiplicativo questo è trascurabile quindi possiamo dire che questo algoritmo viene descritto da $n^2$
2. $T(n)=n\log n+100n$ qui il termine che cresce più velocemente è $n\log n$

Le notazioni asintotiche

Con il termine asintotico indichiamo il comportamento di una funzione quando la variabile indipendente cresce senza limiti, possiamo quindi affermare che:

Una notazione asintotica è un modo sintetico per descrivere il modo in cui una funzione cresce rispetto a un’altra. Essa non ci dice quanto vale esattamente una funzione, ma quanto rapidamente aumenta rispetto ad altre funzioni al crescere di n

Esempio: dire che $T(n)$ è “dell’ordine $n^2$ ” significa che per input molto grandi il numero di operazioni richieste dall’algoritmo cresce in modo proporzionale a $n^2$

In generale le notazioni asintotiche forniscono un linguaggio per esprimere relazioni del tipo:

• $f(n)$ cresce non più rapidamente / alla stessa velocità / più rapidamente di $g(n)$ Esse si basano quindi sul confronto tra le due funzione nel limite per $n\to \infty$ cioè osservando il loro comportamento quando la dimensione diventa molto grande

Esempio: date queste due funzioni: $f(n)=3n^2+5n+7,g(n)=n^2$la differenza può sembrare significativa, ma man mano che $n$ cresce il termine $3n^2$ diventa dominante, quindi possiamo affermare che $f(n)$ e $g(n)$ hanno la stessa crescita asintotica

La notazione Θ (theta)

La notazione $\Theta$ fornisce un vincolo asintotico stretto ovvero rappresenta l’insieme di tutte le funzioni che crescono alla stessa velocità di una funzione di riferimento g(n). Formalmente scriviamo che: $\theta (g(n))=\{f(n)|\exists c_1,c_2,n_0>0\text{ tali che }0\le c_{1}g(n)\le f(n)\le c_{2}g(n),\forall n\ge n_0\}$In altre parole, a partire da una certa soglia $n_0$ la funzione $f(n)$ è sempre compresa tra due multipli costanti della funzione di riferimento $g(n)$. Praticamente la notazione $\Theta$ descrive una crescita bilanciata: $f(n)$ cresce in modo simile a $g(n)$ differendo al più per un fattore costante. Questo significa che per input di $n$ molto grandi possiamo dire che: $\frac{f(n)}{g(n)}\to k\text{ con }0<k<\infty$ da questa immagine capiamo subito il significato della definizione formale infatti dopo un certo $n$ (in questo caso $n=7$) la nostra funzione resta confinata nella fascia delimitata dalla linea tratteggiata

Esempi:

• $5n+20=\theta (n)$ perché la costante additiva non influisce sul comportamento
• $\frac{1}{2}{n}^3+100=\theta (n^3)$

La notazione $\theta$ è la più informativa poiché fornisce sia un limite superiore sia uno inferiore, se $f(n)=\Theta (g(n))$ allora $f(n)$ è simultaneamente:

• $O(g(n))$
• $\Omega (g(n))$ Capiremo successivamente il perché

La notazione O (Big-Oh)

La notazione $O$ rappresenta un limite superiore asintotico ovvero descrive funzioni che per n sufficientemente grandi non crescono più rapidamente di una funzione di riferimento g(n), formalmente si definisce come: $O(g(n))=\{f(n)|\exists c>0,n_0>0\text{ tali che }0\le f(n)\le cg(n),\forall n\ge n_0\}$direi che $f(n)=O(g(n))$ significa che, a partire da una cerca soglia $n_0$ il valore di $f(n)$ non supera mai quello di $cg(n)$

Praticamente la notazione $O$ serve per stabilire una stima superiore del comportamento asintotico infatti garantisce che $f(n)$ non crescerà mai più velocemente di $g(n)$ per $n$ grandi

Attraverso questa immagine riusciamo subito a capire la definizione formale, infatti dopo una $n$ la funzione $f(n)$ non cresce più velocemente di $g(n)$

Esempi:

• $7n+200=O(n)$
• $\log n=O(n)$
• $n=O(n^2)$

la notazione $O$ indica solo un limite superiore se diciamo che $T(n)=O(n^2)$ stiamo affermando che l’algoritmo non richiede mai più di un tempo proporzionale a $n^2$ ma potrebbe essere anche più efficiente. Di solito questa notazione viene usata per descrivere il caso peggiore

La notazione Ω (Big-Omega)

La notazione $\Omega$ rappresenta un limite inferiore asintotico ovvero descrive funzioni che per n sufficientemente grande crescono almeno tanto rapidamente quanto una funzione di riferimento g(n) formalmente si definisce come: $\Omega (g(n))=\{f(n)|\exists c>0,n_0>0\text{ tali che }0\le cg(n)\le f(n),\forall n\ge n_0\}$ Ciò significa che a partire da un certo punto $n_0$ il valore di $f(n)$ è sempre maggiore o uguale a una constante moltiplicativa di $g(n)$

Praticamente la notazione $\Omega$ descrive una crescita minima garantita, infatti oltre una scelta soglia la funzione $f(n)$ rimane sempre al di sopra della funzione di riferimento

Attraverso questa immagine è abbastanza intuitiva la definizione formale, oltre una certa $n$ la nostra funzione $f(n)$ rimane sempre al di sopra della curva $cg(n)$

La notazione $\Omega$ indica un limite inferiore e appunto per questo viene utilizzata per descrivere il caso migliore

Esempi:

• $5n+200=\Omega (n)$
• $n^3=\Omega (n^2)$

Le notazioni o e ω (piccole)

Accanto a $O$ e $\Omega$ che rappresentano limiti asintotici ampi, esistono le loro controparti minuscole $o$ e $\omega$ che esprimo limiti stretti

• La prima $o(g(n))$ esprime che $f(n)$ cresce più lentamente di $g(n)$:$f(n)=o(g(n))\iff \forall c>0,\exists n_o>0\text{ tale che }f(n)<cg(n),\forall n\ge n_o$Significa che il rapporto $\frac{f(n)}{g(n)}$ tende a zero quindi $f(n)$ cresce in modo più lento di $g(n)$ che per $n$ grandi il suo contributo diventa trascurabile

  Praticamente possiamo dire che un tempo di esecuzione $o(n^2)$ significa che esso cresce più lentamente di qualunque funzione proporzionale a $n^2$

• La seconda $\omega (g(n))$ ha un significato opposto descrive infatti funzioni che crescono più rapidamente di $g(n)$:$f(n)=\omega (g(n))\iff \forall c>0,\exists n_0>0\text{ tale che }f(n)>cg(n),\forall n\ge n_0$Significa che il rapporto $\frac{f(n)}{g(n)}$ tende a infinito Praticamente possiamo dire che un tempo di esecuzione $\omega (n^2)$ significa che la nostra funzione cresce più velocemente di qualunque funzione proporzionale a $n^2$

Possiamo dunque pensare alle notazioni $o$ e $\omega$ come versioni esclusive di $O$ e $\Omega$ che indicano una crescita più lenta o più rapida che non raggiunge mai quella della funzione di riferimento

Conclusioni sulle notazioni asintotiche

La scala delle notazioni è la seguente $\omega (g(n))\supseteq \Omega (g(n))\supseteq \Theta (g(n))\subseteq O(g(n))\subseteq o(g(n))$

Oltre i casi limite

Cosa accade davvero in pratica

Le notazioni asintotiche sono strumenti potenti per classificare gli algoritmi, ma è importante ricordare che esse rappresentano un modello astratto del comportamento di un programma. Dire che un algoritmo ha complessità $O(g(n))$ non significa che esegua esattamente $g(n)$ operazioni ma solo che per $n$ grandi il suo tempo di esecuzione non cresce più rapidamente di una funzione $g(n)$, di solito in questo tipo di analisi si distinguono tre casi:

• $O(g(n))$ che descrive il caso peggiore ovvero il limite superiore del tempo di esecuzione
• $\Omega (g(n))$ che descrive il caso migliore ovvero il limite inferiore del tempo di esecuzione
• $\Theta (g(n))$ indica che il tempo di esecuzione è compreso tra i due limiti precedenti, fornisce quindi una descrizione asintoticamente esatta di quello che è il tempo di esecuzione

Esempio 1: La ricerca lineare Nel caso peggiore, una ricerca lineare in un array di $n$ elementi richiede di esaminare tutti gli elementi: $T_{\text{worst}}(n)=O(n)$ Tuttavia, se l’elemento cercato si trova spesso nelle prime posizioni, il numero medio di confronti può essere molto più basso, ad esempio circa $n/2$. In tal caso, il comportamento medio si avvicina a: $T_{\text{avg}}(n)=\Theta (n/2)=\Theta (n)$ ma il tempo effettivo percepito sarà spesso inferiore rispetto al limite teorico.

Esempio 2: L’ordinamento tramite QuickSort Il QuickSort ha una complessità nel caso peggiore di $O(n^2)$, che si verifica quando il pivot scelto in ogni passo è sempre il minimo o il massimo elemento (ad esempio, se l’array è già ordinato). Tuttavia, nella pratica, grazie alla scelta casuale del pivot o a tecniche di bilanciamento, l’algoritmo si comporta quasi sempre come un algoritmo $O(n\log n)$. Il suo caso medio è quindi molto più rappresentativo delle prestazioni reali: $T_{\text{avg}}(n)=\Theta (n\log n)$ Esempio 3: La ricerca binaria La ricerca binaria ha caso migliore $\Omega (1)$ (quando l’elemento cercato è esattamente quello centrale) e caso peggiore $O(\log n)$. Nella pratica, tuttavia, ogni ricerca richiede un numero di passi che dipende in modo logaritmico da $n$, per cui il comportamento effettivo si avvicina costantemente al caso peggiore.

Questi esempi ci mostrano che le notazioni non devono essere interpretate come previsioni puntuali, ma come descrizioni qualitative del comportamento, le notazioni vanno interpretate in questo modo:

• Caso peggio ci garantisce la soglia di sicurezza, utile in contesti critici
• Caso migliore: indica il limite di ottimalità teorica, ma non sempre raggiungibile
• Caso medio: è spesso quello più significativo nella valutazione pratica

Quando le costanti contano

Nell’analisi asintotica degli algoritmi, è prassi trascurare i fattori costanti e i termini di ordine inferiore, questo approccio consente di concentrarsi sulla crescita dominante della funzione per $n$ molto grandi, tuttavia questa cosa nella pratica quotidiana per input di piccole o medie dimensioni dovrebbe essere attenzionata

Esempio: $T_1(n)=100n,T_2(n)=5n{\log }_{2}n$dal punto di vista asintotico $T_1$ è più efficiente, tuttavia il fattore costante $100$ nel primo algoritmo può renderlo più lento del secondo per una vasta gamma di valori realistici di $n$, vediamolo con $n=100$ $T_1(100)=10000,T_2(100)=5\times 100\times {\log }_{2}100\approx 5\times 100\times 6.64=3320$ In questo caso, l’algoritmo con complessità peggiore risulta più veloce. Questo esempio mette in evidenza un punto importante: le notazioni asintotiche descrivono il comportamento per $n$ grandi, ma non sempre riflettono le prestazioni reali su input di dimensioni moderate