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 →).

Complessità 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 \,\}.$$

Altre analisi (caso medio, probabilistica) esistono, ma qui si usa il caso pessimo.

Il metodo pratico. 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). 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: 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 il ciclo interno fa $i+1$ iterazioni, quindi il costo è proporzionale a $\sum_{i=0}^{n-1}(i+1) = \frac{n(n+1)}{2} \in \Theta(n^2)$. Nella seconda si riusa la somma precedente: $\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)$. 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):

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}$.

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)$).