Prendiamo il problema della somma dei primi 100 numeri interi positivi, cioè la somma 1+2+3+...+ 99+100 e pensiamo di risolverlo usando una calcolatrice.
Posso: 1.azzerare il visore, 2.battere e registrare 1, 3.sommare, 4.battere 2, 5.sommare, ..., 198.battere 99, 199.sommare, 200.battere 100, 201.sommare. A questo punto il visore mostra la somma voluta 5050.
Oppure posso conoscere il risultato di Gauss secondo il quale 1+2+3+...+ 99+100 = 50 * 101, e quindi usare la calcolatrice come segue: 1.azzerare il visore, 2.battere e registrare 50, 3. battere 101, 4.fare il prodotto. A questo punto il visore mostra 5050.
I due diversi procedimenti per ottenere la somma voluta sono due strategie o algoritmi differenti di uso della calcolatrice per risolvere lo stesso problema.
Se poi voglio sommare i primi 200 numeri interi le due precedenti strategie adattate al nuovo caso diventano:
- 1.azzerare il visore, 2.battere e registrare 1, 3.sommare, 4.battere 2, 5.sommare, ..., 398.battere 199, 399.sommare, 400.battere 200, 401.sommare. A questo punto il visore mostra la somma voluta 20100.
- 1.azzerare il visore, 2.battere e registrare 100, 3. battere 201, 4.fare il prodotto. A questo punto il visore mostra 20100 cioè 100 * 201.
Ci rendiamo subito conto che la prima strategia richiede più operazioni sulla calcolatrice. Nell’ipotesi che le operazioni richiedano lo stesso tempo, ipotesi molto semplificativa ma che fa al caso nostro, la prima strategia richiede 201 operazioni nel primo caso e 401 nel secondo: all’incirca il doppio come doppio è il numero di addendi della somma voluta nei due casi.
La seconda strategia richiede 4 operazioni in ogni caso, un numero di operazioni costante indipendentemente dal numero di addendi nella somma voluta.
Diremo che la prima strategia ha costo cioè richiede un numero di operazioni proporzionale al numero di addendi da sommare, la seconda strategia ha invece costo costante perché il numero di operazioni è sempre lo stesso a prescindere dal numero di addendi da sommare.
La proprietà di complessità di un algoritmo è nel nostro corso intesa come il costo dell’ algoritmo, come diremo, nel caso peggiore.
A fronte di due o piú differenti strategie è lecito domandarsi se realmente risolvano lo stesso problema: è questa la proprietà di correttezza di un algoritmo di cui diremo precisamente dopo:
· avere illustrato vari esempi di algoritmi specificati in un linguaggio formale particolare (nel nostro caso il Pascal)
· avere imparato a commentare tali algoritmi usando le asserzioni. Per vedere cosa siano i commenti e le asserzioni rimandiamo rispettivamente al punto X.Y e ai capitoli che seguono.