Complessità computazionale

L'efficienza di un metodo dipende, oltre che dalla sua stabilità numerica, anche dal suo costo computazionale (c.c.), cioè dal numero di operazioni aritmetiche elementari che esso richiede.
Di seguito considereremo il numero delle operazioni moltiplicative (cosiddette pesanti),

1. Prodotto matrice-vettore: $A \in \mathbb{R}^{nxm}, x \in \mathbb{R}^n \Rightarrow y = Ax, y \in \mathbb{R}^n $
   $y_i = a_{i1}x_1+a_{i2}x_2+...+a_{in}x_n = \sum\limits_{j=1}^n a_{ij}x_j, \forall i = 1, ..., n$
   Ciascuna componente $y_i$ del vettore $y \in \mathbb{R}^n$ costa $n$ prodotti, le componenti sono $n$
   $ \Rightarrow $ il costo computazionale del prodotto matrice vettore è dell' $O(n^2)$
2. Prodotto righe per colonne: $A, B \in \mathbb{R}^{nxn} \Rightarrow \mathbb{C} = \mathbb{r}^{nxn}$
   $c_{ij} = \sum\limits_{k=1}^n a_{ik}b_{kj}=a_{i1}b_{1j}+a_{i2}b_{2j}+...+a_{in}b_{nj}$
   Abbiamo quindi $n$ prodotti e $n-1$ addizioni (ma come detto prima ci occuperemo solo delle moltiplicazioni).
   Il generico elemento $c_{ij}$ ha un costo computazionale dell'$O(n)$ prodotti. Gli elementi $c_{ij}$ della matrice $C \in \mathbb{R}^{nxn}$ sono in numero $n^2$.
   $\Rightarrow$ il costo computazionale del prodotto righe-colonne tra $A, B \in \mathbb{R}^{nxn}$ è dell'$O(n^3)$.
   
   Se $A \in \mathbb{R}^{mxn}, B \in \mathbb{R}^{nxp} \Rightarrow C = AB \in \mathbb{R}^{mxp}$, il quale c.c. è dell'$O(mnp)$