Complessità

(i,j): il ciclo interno contiene una somma ed un prodotto, $2$ flops, e viene eseguito $n$ volte, $2n$ flops; il ciclo interno è eseguito $m$ volte ottenendo così $2nm$ flops;
(j,i): il ciclo interno esegue $2m$ flops, e viene eseguito n volte, la complessità totale risulta essere $2mn$ flops.

Risulta dunque un algoritmo di ordine quadratico, proporzionale al prodotto delle dimensioni significative; come si vede le due possibili implementazioni hanno medesima complessità, l'unica cosa che cambia è il modo di accesso ai dati.



Morpheus 2004-01-04