Tutti noi sappiamo quanto sia importante in alcune occasioni trovare un algoritmo polinomiale per risolvere un problema (meglio ancora se lineare o logaritmico). Vorrei sottolineare con un taglio matematico quanta rilevanza può avere questa semplice constatazione.
Supponiamo di avere tre algoritmi che risolvono un medesimo problema. Il primo algoritmo ha complessità esponenziale, il secondo ha complessità quadratica e il terzo è lineare. La funzione Ti(n) indica il tempo richiesto dall'algoritmo i-esimo per trovare la soluzione di un problema di dimensione n (in poche parole la complessità dell'algoritmo). Abbiamo quindi:
T1( n ) = 2 ^ n
T2( n ) = n ^ 2
T3( n ) = n
Ci poniamo adesso la seguente domanda: quanti dati ciascuno degli algoritmi precedenti è in grado di elaborare in t unità di tempo ?
La risposta è molto semplice e la soluzione consiste banalmente nel determinare le funzioni inverse a quelle prima elencate.
N1 ( t ) = Log2 ( t )
N2 ( t ) = Sqrt( t )
N3 ( t ) = t
Supponendo di eseguire gli stessi algoritmi su una macchina k volte più veloce la risposta alla precedente domanda sarà il valore delle funzioni Ni(t) calcolate in k * t cioè:
N1 ( k * t ) = Log2 ( k * t ) = Log2 ( k ) + Log2 ( t )
N2 ( k * t ) = Sqrt ( k * t ) = Sqrt ( k ) * Sqrt ( t )
N3 ( k * t ) = k * t
Da ciò risulta molto più evidente la gravità di realizzare algoritmi esponenziali. Nel caso di algoritmi polinomiali il guadagno in termini di quantità di dati trattabili nello stesso tempo è di tipo moltiplicativo. Nel caso di algoritmi esponenziali invece il guadagno è solo di tipo addittivo !!!
In parole più chiare se per assurdo potessimo avere un processore 10000 volte più veloce di quelli attuali, per esempio un processore da 20 Tera Herz ( 10000 volte 2 Giga Hz ) il nostro algoritmo a parità di tempo saprebbe trattare solamente Log2( 10000 ) = 13 dati in più. Il guadagno in termini di scalabilità sui dati è praticamente nullo !!!
Intel come sappiamo ha cambiato rotta nello sviluppo dei suoi processori nella direzione di integrare più core insieme permettendo di fatto un parallelismo reale di esecuzione delle istruzioni. La vera sfida come più volte ha sottolineato Raf ai Community Days 2008 sarà riuscire a scrivere software che sfrutti veramente le nuove architetture multicore. Una sfida sicuramente entusiasmante.
Un problema giocattolo ma particolarmente interessante è il famoso problema della SOTTOSEQUENZA DI SOMMA MASSIMA.
Il problema è il seguente: dato un vettore di numeri interi positivi e negativi determinare la sottosequenza la cui somma è massima.
Diverse sono le possibili soluzioni a questo problema. Due soluzioni immediate ma inefficienti hanno rispettivamente complessità cubica e quadratica. Sfruttando due semplici ma interessanti proprietà è possibile rendere lineare l'algoritmo con indubbi vantaggi sulla velocità di esecuzione e soprattutto sulla scalabilità.
Una semplice applicazione console che realizza e misura le velocità di questi algoritmi la potete trovare nel mio laboratorio online: scarica sottosequenza di somma massima