Complessità computazionale

Definizione 2.16   La complessità computazionale $C(n)$ è il numero di operazioni in virgola mobile (FLOP) coinvolte nell'esecuzione di un algoritmo in funzione della dimensione $n$ dell'input.

Il costo computazionale espresso in operazioni piuttosto che in tempo di esecuzione e' una buona misura perchè è slegato dalla potenza del calcolatore di destinazione, ma non tiene conto del flusso delle istruzioni.

Algoritmi diversi per risolvere lo stesso problema hanno potenzialmente complessità diverse.

Esempio 2.13 (Algoritmo di Hörner)  

Sia $p(x)$ un polinomio qualsiasi

$$p(x) = a_0+a_1x+a_2x^2+...+a_nx^n$$

ll costo del calcolo ``ingenuo'' di $p(x)$ è:

$$C(n) = 3n$$

L'algoritmo di Hörner consiste nel rappresentare il polinomio come:

$$p(x) = ((a_nx+a_{n-1}) + a_{n-2})x + ... a-0$$

Allora è evidente che ogni iterazione costa solo 2 operazioni in virgola mobile al posto di 3, e quindi:

$$C(n) = 2n$$

Esempio 2.14 (Calcolo delle potenze)  

Si vuole calcolare una potenza $a^n$, dove $a \in \mathbb{R},\,n \in \mathbb{N}$.

$$a^n = \underbrace{a \cdot a \cdot \, \dots \, \cdot a}_{n-1 \, prodotti}$$

Una soluzione veloce, che impieghi meno di $n-1$ prodotti, consiste nel suddividere i prodotti in potenze di due.

$$\left. \begin{array}{ll} a \cdot a & = \, a^2 \\ a^2 \cdot a^... ...= \, a^4 \\ \vdots \\ a^{n/2} \cdot a^{n/2} & = \, a^n \end{array}\right\}$$   $\log_2 n$ operazioni

Se $n$ è una potenza di 2, la complessità è

$$C(n) = log_2 n$$

In caso contrario, si può considerare la rappresentazione in base 2 dell'esponente:

$$n = \sum_{j=0}^{m} c_j 2^j$$

$$a^n = a^{c_0} \cdot a^{c_1 2} \cdot a^{c_2 2^2} \cdot \dots \cdot a^{c_m 2^m}$$

$$\left. \begin{array}{ll} a \cdot a & = \, a^2 \\ a^2 \cdot a^... ... \vdots \\ a^{2^{m-1}} \cdot a^{2^{m-1}} & = \, a^{2^m} \end{array}\right\}$$   $m$ operazioni

L'algoritmo impiega $m$ operazioni per calcolare i singoli fattori $a^{c_j2^j}$, e un certo numero di prodotti tra essi per ottenere $a^n$, al più $m$ (se $c_j=0$, si risparmia un prodotto).

La complessità $C(n)$ è quindi al più $2m$.

Esempio 2.15  

Data la seguente matrice

$$A^n, A \in \mathcal{R}^{m \times m}$$

Abbiamo che

$$A^n = \prod_{j=0}^m A^{2^j} +$$   eventuali m prodotti di matrici$$$$

Per $m=10^2$ il calcolo del prodotto ha costo $O(10^6)$ FLOPS, mentre per $m=10^3$ il calcolo del prodotto ha costo $O(10^9)$ FLOPS.

$$(AB)_{ij} = \sum^{m}_{k=1}a_{ik}b_{kj}$$

Ha costo $\approx$ 2 MFLOPS.

Esempio 2.16  

Consideriamo il problema di calcolare $e^x$. Sia $a > 0$, allora è noto che

$$a^n = e^{n\log a}$$

$$f(x) = e^{x}, x > 0$$

Consideriamo la serie di Taylor corrispondente (con resto di Lagrange):

$$e^x = e^0 + e^0x + e^0 \frac{x^2}{2} + e^0 \frac{x^3}{3!} + \ldots + e^0 \frac{x^m}{m!} + \overbrace{R_m(x)}^{\frac{e^\xi x^{m+1}}{(m+1)!}}$$

$R_m(x) = \frac{e^\xi x^{m+1}}{(m+1)!}$ con $\xi \in (0,x)$ converge a 0 per $m \to \infty$, $x \in [0,1]$.

$$f(x) = f(x_0) + f'(x_0)(x-x_0) + \frac{f''(x_0)(x-x_0)^2}{2} + \f... ... + \ldots + \frac{f^{m}(x_0)(x-x_0)^m}{n} +\underbrace{R_m(x)}_{\text{errore}}$$

Con $f \in C^{n+1}(I_{x_0})$ (f derivabile n+1 volte nell'intorno di $x_0$).

$$R_m(x) = \frac{f^{m+1}(\xi)}{(m+1)!}(x-x_0)^{m+1}$$ con $$\xi \in (x_0, x)$$

Vicino a 0 l'espansione di Taylor funziona bene:

$$0 \leq R_m(k) \leq \xi e^b \underbrace{\frac{b^{m+1}}{(m+1)!}}_{\to 0}$$

Stima dell'errore:

$$e^x = T_m(x) + R_m(x)$$

$$R_m(x) = \frac{e^\xi x^{m+1}}{(m+1)!} \leq \underbrace{\frac{e^x x^{m+1}}{(m+1)!}}_{\underset{m\to\infty}{\to 0}}$$

$$\frac{\vert e^x-T_m(x)\vert}{\vert e^x\vert} = \frac{e^\xi x^{m+1} }{(m+1)!}$$

$$\begin{cases} 0 < x < 1 : \varepsilon_x \leq \underbrace{\fr... ...ac{1}{m!} \approx \varepsilon_m \text{ per } m = 18 \end{cases}$$

Il caso due si puo' risolvere agevolmente con la seguente astuzia:

$$e^x = (e^{\frac{x}{n}})^n = a^n = (e^y)^n$$

dove

$$a^{\frac{x}{n}} = a^y$$

con $0 \leq y \leq 1$, $n = [x] + 1$ Il che equivale a trovarsi sempre nel caso 1 con l'aggiunta di una potenza rapida.

Esempio 2.17 (Sviluppo di Laplace)  

Consideriamo il problema di calcolare il determinante di una matrice $A \in \mathbb{R}^{n \times n}$.

La sviluppo di Laplace è un metodo particolarmente inefficiente di calcolare il determinante³:

$$\det(A) = \sum_{j=1}^{n} (-1)^{i+j} a_{i,\,j} \det(A_{i,\,j})$$

dove $A_{i,\,j}$ è una matrice $\mathbb{R}^{(n-1)\times(n-1)}$ ottenuta da $A$ cancellando la riga $i$-esima e la colonna $j$-esima.

Il costo del calcolo del determinante di $A$ con Laplace è $C(n) \approx 2n!$ e il numero di moltiplicazioni necessario è $\approx n^n$.

n	t @ 1GFLOPS	t @ 1TFLOPS
10	4 ms	-
15	24 minuti	-
20	154 anni	$\approx$ 2 mesi
25	$10^9$ anni	$10^6$ anni
100	$10^{141}$ anni	$10^{13}$ anni

<>

Esempio 2.18 (MEG)   Il metodo di eliminazione di Gauss è un algoritmo per risolvere sistemi di equazioni lineari per mezzo di una sequenza di operazioni (mosse di Gauss) operate sulla matrice associata.

$$A \overset{MEG}{\to} U$$

Dove $\overset{MEG}{\to}$ è una sequenza di mosse di Gauss risulta in una matrice triangolare superiore $U$ tale che $\det A = \pm \det U = \pm \prod_{i = 1}^n a_{ii}.$

Ricordiamo le proprietà del determinante:

• Dato $R_k = R_k + \alpha R_i$ il determinante non cambia. Significa che se sommo o sottraggo ad una riga (colonna) una qualunque riga (colonna) moltiplicata per un numero $\alpha$ il determinante non cambia;
• Scambiando due righe $R_i$ (oppure due colonne $R_j$) il determinante cambia segno.

$$\begin{split} \left(\begin{matrix} 1&2&1\\ 2&2&3\\ -1&-3&0... ...\\ 0 & 0 & \nicefrac{1}{2} \end{matrix}\right) = U \end{split}$$

Non c'è stato scambio di righe, dunque il determinante di U vale

$$\det U = -1 = \det A$$

L'algoritmo del MEG è un algoritmo finito, ma delicato da trattare in aritmetica di macchina.