Complessità asintotica

Per misurare l'efficienza di un particolare algoritmo, a prescindere dalla macchina utilizzata, bisogna valutare l'utilizzo di memoria e di tempo da parte dell'algoritmo in funzione dell'input.

Per poter studiare come aumentano il tempo e la memoria all'aumentare dell'input, bisogna rifarsi alla stima asintotica, introduciamo quindi 3 nuove notazioni:

Espressioni asintotiche: O, Ω, Θ

O (o grande), Ω (omega grande), Θ (theta grande) sono le tre espressioni asintotiche che utilizzeremo per studiare i diversi algoritmi. Queste espressioni servono per studiare quanto una funzione è simile ad un'altra, più conosciuta (si farà sempre riferimento a queste classi di funzioni: logaritmiche, polinomiali ed esponenziali; è necessario conoscere le principali caratteristiche di queste funzioni per poter comprendere il resto della lezione). Queste sono le definizioni matematiche che useremo cum grano salis:

O grande

Siano f e g due funzioni definite su $\mathbb {N}$ a valori in $\mathbb {R}$.

Si dice che f(n) è un o-grande di g(n), in simboli

$f(n)\in O(g(n))$

se $\exists c>0,n_{0}\in N:\forall n\geq n_{0},|f(n)|\leq c|g(n)|$.

Si dice anche che f(n) ha ordine di grandezza minore o uguale a quello di g(n), cioè la funzione g(n) domina f(n).

Se la successione g(n) ha valori definitivamente diversi da 0, una condizione equivalente, sfruttando il limite superiore, è che sia $\limsup _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty .$

Omega grande

Si dice che f(n) è un omega grande di g(n), in simboli

$f(n)\in \Omega (g(n))$

se $\exists c>0,n_{0}\in N:\forall n\geq n_{0},|f(n)|\geq c|g(n)|$.

Si dice anche che f(n) ha ordine di grandezza maggiore o uguale a quello di g(n), o che g(n) è dominata da f(n).

Usando la notazione del limite inferiore, una condizione equivalente è che sia $\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|>0$

Relazione Theta

f(n) e g(n) sono dette avere lo stesso ordine di grandezza, in simboli

$f(n)\in \Theta (g(n))$

se $\exists c_{1},c_{2}>0,n_{0}\in N:\forall n\geq n_{0},c_{1}|g(n)|\leq |f(n)|\leq c_{2}|g(n)|$.

Usando i limiti superiore e inferiore, questa condizione si può enunciare come $0<\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|\leq \limsup _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty$

Applicazioni agli algoritmi

Possiamo riassumere queste definizioni in questo modo:

• $F(n)\in O(g(n))$ se $f(n)$ non cresce più di un multiplo di $g(n)$ per n abbastanza grandi
• $F(n)\in \Omega (g(n))$ se $f(n)$ cresce sempre più di un multiplo di $g(n)$ per n abbastanza grandi
• $F(n)\in \Theta (g(n))$ se $f(n)$ è sia $O(g(n))$ sia $\Omega (g(n))$ di multipli (distinti) di $g(n)$ per n abbastanza grandi

È molto utile ricordare i diversi ordini di infinito:

$log_{a}{n}\leq n^{b}\leq c^{n}\leq n!\leq n^{n}$

Questo significa che un algoritmo di complessità (spaziale o temporale) $log_{a}{n}$ è più efficiente di un algoritmo di complessità $a^{n}$ (dove n solitamente è la dimensione dell'input e ovviamente a è positivo e maggiore di 1).

Molto spesso si parlerà di complessità $nlog_{2}{n}$ detta "pseudo-lineare"; l'ordine di questo infinito è poco superiore al lineare e inferiore a qualsiasi potenza maggiore di 1: ossia $\Omega (n)$ e $O(n^{b})$ con $b>1$.

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). Tuttavia T(n) e S(n) non sono vere funzioni, infatti per la medesima n possono avere risultati completamente diversi (esempio: utilizzando la ricerca binaria, a prescindere dalle dimensioni dell'array, se si cerca il valore mediano si eseguirà solo un controllo, dunque T(n)= costante ).

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. In questo modo si hanno 3 funzioni (sia per il tempo che per lo spazio) univocamente determinate; molto spesso queste funzioni non sono riconducibili a funzioni elementari, ma il loro andamento asintotico è uno di quelli appena descritti.

Caso migliore, caso peggiore e caso medio

Più precisamente: Sia A un algoritmo descritto in modo informale oppure un programma scritto in un vero linguaggio di programmazione. Sia X un possibile insieme di dati in ingresso adatta all'esecuzione dell'algoritmo (ad esempio, per un algoritmo operante su un array, X è il particolare array passato all'algoritmo). Siano:

• $T(X)=$tempo di esecuzione dell'algoritmo per l'input X;
• $S(X)=$spazio di memoria necessario (in aggiunta allo spazio occupato dal dato stesso in ingresso I) per l'esecuzione dell'algoritmo per l'input X;
• $N_{X}=$dimensione dell'input X, espressa in unità convenienti.

$t(X)$ ed $s(X)$di solito dipendono da $n_{X}$, ma non solo da $n_{X}$. I tre casi possono essere riassunti in questo modo:

• Caso peggiore: $T_{p}(n)=max\lbrace t(X)|$X di dimensione n $\rbrace$
• Caso migliore: $T_{m}(n)=min\lbrace t(X)|$X di dimensione n $\rbrace$
• Caso medio: $T_{a}(n)=avg\lbrace t(X)|$X di dimensione n $\rbrace$ (Notare che è una media ponderata sulle probabilità con cui si possono verificare i diversi input)

In tale modo, per ogni n, $T_{p}(n),T_{m}(n)$ e $T_{a}(n)$ sono univocamente determinati e sono vere funzioni in n (analogo discorso per $S_{p}(n),S_{m}(n)$ e $S_{a}(n)$).

Delimitazioni Superiori e Inferiori di un algoritmo

Ovviamente esistono, dato un algoritmo, una serie di combinazioni possibili di complessità nel caso peggiore, migliore o medio. Vanno però notate alcune ovvie proprietà:

• Se $T_{p}(n)$ è $O(f(n))$ allora $T_{a}(n)$ è $O(f(n))$ e $T_{m}(n)$ è $O(f(n))$.

Ossia se nel caso peggiore l'algoritmo cresce non più di una funzione $f(n)$ allora i casi migliore e medio cresceranno meno del caso peggiore, ed in particolare, meno di tale funzione $f(n)$.

• Se $T_{m}(n)$ è $\Omega (f(n))$ allora $T_{a}(n)$ è $\Omega (f(n))$ e $T_{p}(n)$ è $\Omega (f(n))$.

Ossia se il caso migliore cresce almeno quanto una certa funzione $f(n)$ allora anche il caso peggiore crescerà almeno quanto tale funzione.

Possiamo generalizzare (uscendo dal rigore matematico) dicendo che

• Il tempo di esecuzione di un algoritmo è $O(f(n))$ se $T_{p}(n)$ è $O(f(n))$
• Il tempo di esecuzione di un algoritmo è $\Omega (f(n))$ se $T_{m}(n)$ è $\Omega (f(n))$

Il tempo di esecuzione di un algoritmo è $\Theta (f(n))$ se è sia $O(f(n))$ che $\Omega (f(n))$

Un esempio: l'insertion sort

L'insertion sort è un algoritmo di ordinamento. Tale algoritmo ha una complessità nel caso peggiore (che corrisponde, solitamente, ad un array con elementi inseriti in ordine inverso) pari a $\Theta (n^{2})$, quindi anche $O(n^{2})$, perciò possiamo dire che il tempo di esecuzione dell'algoritmo è $O(n^{2})$. Nel caso migliore (che come vedremo, corrisponde all'array già ordinato) è $\Theta (n)$, quindi anche $\Omega (n)$. Dunque il tempo di esecuzione dell'algoritmo è $\Omega (n)$.

Complessità dei problemi

Studiare la complessità di un problema (ossia quello che un algoritmo risolve) è molto diverso dallo studiare la complessità di un algoritmo. Per poter dire che un problema ha complessita O(f(n)) (ipotizziamo di parlare del caso peggiore) basta trovare un qualsiasi algoritmo che lo risolva con O(f(n)). Per poter affermare che un problema è Ω(f(n)) occorre invece dimostrare matematicamente che tutti i possibili algoritmi (inventati o non) lo risolvano alla meglio come Ω(f(n)).

Dunque per limitare superiormente un problema basta trovare almeno un algoritmo con complessità O(f(n)), invece per limitare il problema inferiormente bisogna studiare ogni possibile soluzione (il problema, in linea teorica, potrebbe essere risolto in tempo costante, ma si può sempre dimostrare il contrario).

Un esempio: l'ordinamento

Sapendo che esiste un algoritmo (ad esempio il Quick Sort) che risolve il problema dell'ordinamento in un tempo $\Omega (nlogn)$ possiamo facilmente dire che il limite superiore dell'ordinamento è $nlogn$. Tuttavia non sappiamo ancora se possa esistere un algoritmo ancora più veloce, ma possiamo immaginare che per ordinare un array bisogna almeno leggere una volta tutti gli elementi (se non altro per metterli al posto giusto); dunque una prima intuizione matematica ci fa pensare che il limite inferiore dell'ordinamento sia lineare in $n$. A questo punto si presenta un gap: il limite superiore è diverso da quello inferiore per un ordine di infinito ($nlogn$ cresce più di $n$). L'esistenza di questo gap può voler dire due cose: o esiste un algoritmo più veloce, che risolve il problema dell'ordinamento in tempo lineare oppure è da dimostrare (ma, in generale, non è certo che la dimostrazione esista) che $nlogn$ è il limite inferiore.

Problemi insolubili

Esistono, per concludere il discorso, problemi (rigorosamente specificati) non risolvibili dai calcolatori. Uno di questi può essere enunciato nel seguente modo: "Dati due programmi scritti in un linguaggio di programmazione (reale o ipotetico) stabilire se sono equivalenti: ossia se per ogni input restituiscono lo stesso output". Per tali problemi è stato dimostrato non possa esistere nessun algoritmo risolvente.

Riassumendo, ad oggi, si presentano situazioni diverse per diversi problemi algoritmici:

• Problemi risolti da un algoritmo "veloce" (logaritmico, lineare, pseudolineare) e per i quali si è dimostrato che non possono esistere algoritmi asintoticamente migliori (problemi "facili" chiusi); esempio: il problema dell'ordinamento;
• Problemi risolti da un algoritmo efficiente o comunque polinomiale, che però non si sa se sia quello asintoticamente migliore (problemi trattabili, con gap algoritmico); esempio: il prodotto di matrici;
• Problemi "presumibilmente" intrattabili: problemi per i quali gli unici algoritmi risolventi sono esponenziali, e per i quali si sospetta fortemente – ma non si è dimostrato – che non esistano algoritmi migliori; esempi: soddisfacibilità booleana, problema del commesso viaggiatore;
• Problemi dimostrabilmente intrattabili: problemi per i quali gli unici algoritmi risolventi sono esponenziali, e per i quali si è dimostrato che non possono esistere algoritmi migliori; esempi: le torri di Hanoi, il problema dei blocchi stradali;
• Problemi dimostrabilmente insolubili: problemi per i quali si è dimostrato che non possono esistere algoritmi risolventi; esempi: il problema della terminazione, il problema dell'equivalenza fra programmi.