Complessità in tempo e caso pessimo

Perché serve un'analisi teorica

Il tempo di esecuzione di un programma dipende dall'istanza (a parità di taglia, input diversi possono costare molto diversamente: pensa a InsertionSort su un array già ordinato o invertito), dall'hardware e dal software. Misurarlo (in Java con System.currentTimeMillis() prima e dopo l'esecuzione) ha limiti: non copre tutti gli input, richiede di implementare l'algoritmo, e il confronto tra algoritmi dipende da macchina e implementazione.

Servono quindi un'analisi che consideri tutti gli input, permetta di confrontare algoritmi senza il tempo esatto, e parta dallo pseudocodice. L'approccio: caso pessimo in funzione della taglia, conteggio di passi nel modello RAM (vedi Problemi computazionali e algoritmiProblema computazionale come insieme di coppie (istanza, soluzione); algoritmo e modello di calcolo RAM; pseudocodice; taglia di un'istanza; ADT e struttura dati concreta; esempio svolto con ricerca lineare e binaria in un array ordinato.Problemi computazionali e algoritmi →), analisi asintotica (vedi Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →). In Fondamenti di Informatica lo stesso tema è trattato in modo più elementare in Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →; qui si formalizza.

Complessità al caso pessimo

Definizione (complessità in tempo al caso pessimo). Sia $t_{A,i}$ il numero di operazioni eseguite da $A$ sull'istanza $i$. La complessità in tempo al caso pessimo è

$$t_A(n) = \max\{\, t_{A,i} : i \in I,\ i \text{ ha taglia } n \,\}.$$

Esempio. InsertionSort su $n=4$ elementi fa $3$ confronti sull'array ordinato $[1,2,3,4]$ e $6$ sull'array invertito $[4,3,2,1]$: il caso pessimo è il massimo, $6$.

Altre analisi (caso medio, probabilistica) esistono, ma qui si usa il caso pessimo. Il caso medio richiede di assegnare una probabilità a ciascuna istanza e di calcolare un valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso → del costo; il caso pessimo no, ed è una garanzia valida per qualunque input.

Proprietà (stima con limiti superiore e inferiore). Trovare l'istanza peggiore e contare i passi esatti è difficile e inutile. Si cercano due funzioni semplici:

• limite superiore $t_A(n) \in O(g(n))$: si argomenta che per ogni $n$ abbastanza grande, ogni istanza di taglia $n$ costa al più $c\,g(n)$ operazioni;
• limite inferiore $t_A(n) \in \Omega(g(n))$: si argomenta che per ogni $n$ abbastanza grande esiste un'istanza di taglia $n$ che costa almeno $c\,g(n)$ (a volte è comodo mostrare che tutte le istanze costano tanto).

Se coincidono si ha $\Theta(g(n))$ (stima stretta; le definizioni di $O$, $\Omega$ e $\Theta$ con le costanti $c$ ed $n_0$ sono in Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →). La funzione $g$ deve essere la più vicina possibile al vero andamento (tight) e la più semplice (niente costanti, niente termini di ordine inferiore).

Esempio. Se ogni istanza di taglia $n$ costa al più $c_1n+c_2$ operazioni e una di esse ne costa almeno $c_3n$, allora $t(n)\in O(n)\cap\Omega(n)=\Theta(n)$.

Esempio: arrayMax

Algoritmo arrayMax(A, n)
Input: array A di n >= 1 interi
Output: massimo di A
currMax <- A[0]
for i <- 1 to n-1 do
    if currMax < A[i] then currMax <- A[i]
return currMax

Fuori dal ciclo ci sono operazioni in numero costante; il ciclo fa $n-1$ iterazioni, ciascuna di costo costante. Esistono quindi $c_1, c_2, c_3, c_4 > 0$ con $c_3 n + c_4 \le t(n) \le c_1 n + c_2$: $t(n) \in \Theta(n)$. Non servono i valori delle costanti.

Esempio: prefix averages

Dato $X[0..n-1]$, calcolare $A[i] = \frac{1}{i+1}\sum_{j=0}^{i} X[j]$.

prefixAverages1(X, n)            prefixAverages2(X, n)
for i <- 0 to n-1 do             s <- 0
    a <- 0                       for i <- 0 to n-1 do
    for j <- 0 to i do               s <- s + X[i]
        a <- a + X[j]                A[i] <- s / (i+1)
    A[i] <- a / (i+1)            return A
return A

Nella prima versione, per ogni valore di $i$ il ciclo interno ($j$ da $0$ a $i$) fa $i+1$ iterazioni. Il costo totale è quindi proporzionale a $$\sum_{i=0}^{n-1}(i+1) = \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \in \Theta(n^2),$$ dove si è posto $k=i+1$ (la somma passa da $i=0..n-1$ a $k=1..n$) e si è usata la somma dei primi $n$ interi (vedi SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →; la formula si dimostra per induzione: Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →). Ad esempio per $n=4$: $1+2+3+4=10=\frac{4\cdot5}{2}$. Il termine $\frac{n(n+1)}{2}=\frac{n^2}{2}+\frac{n}{2}$ è un polinomio di grado $2$, quindi $\Theta(n^2)$. Nella seconda si riusa la somma precedente: s contiene già $X[0]+\dots+X[i-1]$, basta aggiungere $X[i]$ (una sola addizione) invece di rifare tutte le $i+1$; il ciclo fa $n$ iterazioni di costo costante, $\Theta(n)$. Stesso problema, algoritmi di efficienza molto diversa.

Esempio: InsertionSort

Algoritmo InsertionSort(S)
for i <- 1 to n-1 do
    curr <- S[i]; j <- i-1
    while j >= 0 AND S[j] > curr do
        S[j+1] <- S[j]; j <- j-1
    S[j+1] <- curr

• Ogni istanza di taglia $n$ esegue al più $c\,n^2$ operazioni: ciclo esterno $n-1$ volte, interno al più $i$ volte, $\sum i = O(n^2)$. Quindi $f_1(n) = n^2$.
• Ogni istanza esegue almeno $c\,n$ operazioni (il ciclo esterno gira sempre $n-1$ volte): $f_2(n) = n$.
• Esiste un'istanza con $c\,n^2$ operazioni: l'array in ordine decrescente, dove ogni elemento percorre tutto il prefisso ($\frac{n(n-1)}{2}$ confronti; verificato: per $n=10$ sono $45$). $f_3(n) = n^2$.

Da $f_1$ e $f_3$: $t_{IS}(n) \in O(n^2) \cap \Omega(n^2) = \Theta(n^2)$.

Perché $\frac{n(n-1)}{2}$ sull'array decrescente. All'iterazione $i$ (con $i=1,\dots,n-1$) l'elemento curr = S[i] è minore di tutti i precedenti, quindi S[j] > curr è vero per $j=i-1,\dots,0$: si contano $i$ confronti (più uno finale quando $j$ esce dall'array, che non confronta nulla). In totale $\sum_{i=1}^{n-1} i = \frac{(n-1)n}{2}$ (stessa somma, vedi SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). Traccia su $n=4$, array $[4,3,2,1]$:

Totale $1+2+3=6=\frac{4\cdot3}{2}$, come nell'esempio sopra. Sull'array già ordinato ogni curr è maggiore del precedente, il test fallisce subito e si fa un solo confronto per iterazione: $n-1$ in tutto. Sull'array già ordinato servono solo $n-1$ confronti: per questo si parla di caso pessimo.

Efficienza asintotica e tempi

Se $t_A(n) \in o(t_B(n))$ allora $A$ è asintoticamente più efficiente di $B$. Regola pratica: complessità polinomiale (o migliore) $\Rightarrow$ algoritmo efficiente; esponenziale $\Rightarrow$ inefficiente. Taglia massima $n_\tau$ risolvibile in tempo $\tau$ (con $t_A$ in nanosecondi):

Come si leggono i numeri. Un secondo sono $10^9$ ns, un minuto $6\cdot10^{10}$ ns, un'ora $3{,}6\cdot10^{12}$ ns. Per $t_A(n)=n$ si risolve $n \le \tau$ e basta. Per $t_A(n)=n^2$ si risolve $n^2 \le \tau$, cioè $n \le \sqrt{\tau}$: $\sqrt{10^9}\approx 31\,623$, $\sqrt{6\cdot10^{10}}\approx 244\,949$, $\sqrt{3{,}6\cdot10^{12}}\approx 1{,}9\cdot10^6$. Per $t_A(n)=2^n$ si risolve $2^n \le \tau$, cioè $n \le \log_2 \tau$ (vedi Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →): $\log_2 10^9\approx 29{,}9$, $\log_2(6\cdot10^{10})\approx 35{,}8$, $\log_2(3{,}6\cdot10^{12})\approx 41{,}7$. Per $t_A(n)=\log_2 n$ la condizione $\log_2 n \le \tau$ dà $n \le 2^{\tau}$, un numero con miliardi di cifre. Il messaggio: moltiplicare per 3600 il tempo a disposizione (da 1 s a 1 ora) fa passare l'algoritmo esponenziale da $n\approx30$ a $n\approx42$, mentre quello quadratico guadagna un fattore $60$ sulla taglia.

Limiti dell'analisi

• Caso pessimo: può riguardare istanze patologiche mentre quelle di interesse costano meno (esempio: QuickSort); si può restringere il dominio delle istanze o analizzare il caso medio.
• Asintotica: le costanti ignorate possono contare. $t_A(n) = 10^{100} n$ è $\Theta(n)$ e $t_B(n) = n^2$ è peggiore asintoticamente, ma $t_A < t_B$ solo per $n > 10^{100}$, cioè mai in pratica. Così $400 \log_2 n$ batte $\log_2^2 n$ solo per $n > 2^{400}$: infatti $\log_2^2 n > 400\log_2 n \iff \log_2 n > 400 \iff n > 2^{400}$ (dividendo per $\log_2 n > 0$). Il confronto tra le funzioni per $n \to \infty$ è lo stesso della gerarchia degli infinitiI limiti di base per sciogliere le forme indeterminate delle successioni: potenze, polinomi, il numero e, esponenziali, la gerarchia logaritmi < potenze < esponenziali < fattoriale < n^n e la razionalizzazione.Limiti notevoli e gerarchia degli infiniti → vista in Analisi 1.

Errori comuni

• Dire "$B$ è sempre più veloce di $A$" perché $n \log n < n^2$: l'asintotica vale per $n$ grandi, le costanti contano per $n$ piccoli.
• Calcolare il caso pessimo scegliendo un'istanza a caso, o provare solo il limite superiore e dichiarare $\Theta$.
• Mettere costanti o termini minori nel risultato ($\Theta(3n + 2)$ invece di $\Theta(n)$).