Complessità: prodotto di matrici

Nel prodotto tra matrici di dimensioni nxn, C=AxB, è richiesto almeno il tempo

T₁(n) = c₁ · n², per scrivere i risultati in C
T₂(n) = 2 · c₂ · n², per leggere i dati in A e B

Non può esistere un algoritmo con complessità inferiore a quella necessaria per esaminare l’input oppure per generare l’output e quindi si parte comunque da una complessità quadratica.

L’algoritmo tradizionale che calcola il singolo elemento c_ij tramite il prodotto scalare

c_ij = a_i · b_j = a_i1 · b_1j + a_i2 · b_2j + … + a_in · b_nj

richiede n moltiplicazioni per ogni prodotto scalare e quindi richiede

T₃(n) = c₃ · n · n² = c₃ · n³

per calcolare tutti i prodotti.

Questo algoritmo ci permette di stabilire un limite superiore per la complessità del problema.

In conclusione

T₁(n) ≤ T₂(n) ≤ T(n) ≤ T₃(n)

c₂ · n² ≤ T(n) ≤ c₃ · n³

Il problema del prodotto matriciale ha una complessità compresa tra O(n²) e O(n³) per il numero di prodotti.

Miglioramento?

Esistono effettivamente algoritmi che abbassano la complessità da $O\left(n^{3}\right)$ a $O\left(n^{2,8074}\right)$ .
Vedi Algoritmo di Strassen.

Il miglioramento potrebbe sembrare impercettibile ma al crescere di n diventa significativo…

n	$T(n)$	$T_3(n)$	$\displaystyle \frac{T(n)}{T_3(n)}$
10¹	~6,42 * 10²	10³	64 %
10²	~4,12 * 10⁵	10⁶	41 %
10³	~2,64 * 10⁸	10⁹	26 %
10⁴	~1,70 * 10¹¹	10¹²	17 %
10⁵	~1,09 * 10¹⁴	10¹⁵	11 %

Osserva

per n = 1.000 il tempo si riduce a un quarto
per n = 10.000 il tempo si riduce a un sesto