Costo degli algoritmi
Abbiamo visto che dato un problema esistono diversi algoritmi che lo risolvono:
- e per ogni algoritmo più programmi che lo implementano (con diversi gradi di efficienza).
Come scegliere l’algoritmo (o il programma) più adatto?
Ogni programma necessita di una certa quantità di memoria ed impiega una certa quantità di tempo per essere eseguito.
Le risorse tempo e spazio di memoria sono spesso in conflitto:
- aumentando la memoria occupata dal programma si può diminuire il tempo di calcolo.
Costo degli algoritmi (segue)
Ci occuperemo della valutazione dell’efficienza o complessità di un programma in termini del solo tempo di calcolo trascurando la quantità di memoria utilizzata e supponendo quindi che non ci sia alcun limite alla quantità di memoria utilizzata dal programma.
Costo degli algoritmi (segue)
La complessità di un algoritmo è una stima quantitativa di come varia il tempo di calcolo al variare della dimensione dei dati di input
Il tempo di calcolo di un programma su un particolare calcolatore dipende:
- dai dati di input:
- dimensione, caratteristiche come ordinamento, compattezza, etc;
- dalla complessità delle istruzioni;
- dalla quantità di memoria usata dal programma:
- se è limitata o se dipende da altri programmi in esecuzione;
- dalla velocità di esecuzione delle operazioni elementari:
- addizione, moltiplicazione, valutazione delle espressioni booleane, etc;
- dalla velocità di accesso alla memoria e ai dispositivi di I/O;
- …
Valutiamo l’efficienza di un programma solo determinando la complessità del suo algoritmo.
Costo degli algoritmi (segue)
Sia Ik una istruzione del programma PG :
- Ik= ek espressione elementare
- assegnazione di costante, espressione semplice.
- Ik= Ek espressione composta
- assegnazione di espressione, espressione composta, etc.
- Ik= Bk istruzione composta
- blocco (sequenza) di istruzioni: corpo di funzione, di cicli, etc.
- Ik= Fk costrutto di controllo
- for(), while () …, if () else () , etc.
Sia C(Ik) la funzione che associa un numero intero (tempo di calcolo) all’esecuzione di ogni istruzione del programma
funzione di costo C(Ik) = n C : PG → N
Costo degli algoritmi (segue)
Sia e una espressione elementare:
- singola assegnazione con r-value costante o singola variabile:
x ← 4
y ← z
- espressione semplice:
3 + x
Y
- espressione booleana semplice:
a and b
- accesso a elemento di array A[i,...,k] con indici costanti:
matrice[3,j]
Costo degli algoritmi (segue)
Sia E una espressione composta:
- assegnazione con espressione a destra: x ← E (istruzione semplice):
x ← y + 3
- accesso a elemento di array A[E1,...,Ek] con uno o più indici di tipo espressione:
tabella[4+i,j]
- composizione di espressioni: E1 and Ek
(x * 3) > (y / 2)
Costo degli algoritmi (segue)
Sia B un blocco di istruzioni:
- una sequenza di istruzioni B = E1,E2,….,En che compongono il corpo di un ciclo, una funzione, di un if etc.
Costo degli algoritmi (segue)
Sia F una istruzione di controllo di selezione:
- F = if (E) {B}
C(F) = C(E) + C(B)
- F = if (E) {B1} else {B2 }
C(F) = C(E) + max(C(B1), C(B2))
Costo degli algoritmi (segue)
Sia F una chiamata di funzione:
- F = foo(x1,…,xn)
foo(x1,…,xn){
B
return Ek}
Costo degli algoritmi (segue)
Sia F una istruzione di controllo di iterazione.
Costo degli algoritmi (segue)
Sia F una istruzione di controllo di iterazione
- F = while (E) {B}
- C(F) = C(E) + M · [C(E)+C(B)]
- F = do {B} while (E)
- C(F) = M · [C(E)+C(B)]
- Dove M è il massimo numero (se esiste) di iterazioni possibili.
- Se è possibile determinare il maggiorante M questo deve riferirsi al caso peggiore (è quello che interessa nello studio dell’efficienza degli algoritmi);
- ci sono casi in cui è impossibile determinare M (è anche impossibile determinare se il ciclo termina o no).
Costo degli algoritmi (segue)
In altri termini non esiste alcun algoritmo in grado di determinare, dato un qualsiasi while loop quanto vale il massimo numero di iterazioni ed in particolare non esiste un algoritmo in grado di decidere, dato un qualsiasi while loop, se questo termina sempre in un numero finito di passi oppure no. Un tipico esempio si basa sulla:
Congettura di Collatz: partendo da un numero naturale qualsiasi a>0 e applicando la regola mostrata nella figura a lato, si raggiunge sempre il valore 1.
Costo degli algoritmi (segue)
Per esempio, iniziando con n = 6, otteniamo la sequenza:
6, 3, 10, 5, 16, 8, 4, 2, 1.
La congettura di Collatz asserisce che questo algoritmo giunge sempre a termine, indipendentemente dal valore di partenza.
La congettura risulterebbe quindi falsa se esistesse una sequenza che non contiene l’1.
Costo degli algoritmi (segue)
La congettura di Collatz non è stata dimostrata. Pertanto non si è in grado di stabilire se la complessità della function mostrata nella figura a lato è infinita oppure no.
Costo degli algoritmi (segue)
Esempio: calcoliamo la complessità dell’algoritmo della radice quadrata, come mostrato in figura.
C(B1) = 3 (inizializzazione di Xs, eps, lettura a)
C(B2) = 5 (assegnazioni di Xp, calcolo nuovo Xp e assegnazione Xs)
C(B3) = 1 (stampa risultato)
C = 3 + C(do {B2} while(E)) + 1 = 3 + M _ (5 + 3) + 1 = 3 + 8M + 1
Esempio
Calcoliamo il costo dell’algoritmo di Bubble-Sort.
for(k=0; k=k; j–)
if (vet[j] > vet[j+1])
scambia (vet[j],vet[j+1]);
for (j=N-2; j>=k; j–)
Il caso peggiore dell’Bubble sort è quando il vettore iniziale ha elementi tutti diversi ed è già ordinato ma in senso decrescente.
In questo caso accade che, ad ogni iterazione k del ciclo esterno, si ha il numero massimo di scambi (n-1+k), ossia tutti le coppie sono scambiate perché diverse e ordinate in senso inverso.
N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2
Esempio (segue)
Calcoliamo il costo dell’algoritmo di Bubble-Sort.
for(k=0; k<N-1; k++)
for (j=N-2; j>=k; j–)
if (vet[j] > vet[j+1])
scambia (vet[j],vet[j+1]);
Come primo passo determiniamo il costo della funzione scambia(x,y).
Esso sarà pari a 2 più il costo del corpo della funzione che comprende tre assegnazioni; quindi:
C(scambia)=9+2
Ancora, il costo della condizione relativa all’istruzione if è :
C(if) = 1 + C(scambia) = 12
Tale costo è anche il costo del corpo del loop interno ed è indipendente dall’indice j.
Siccome il corpo del for interno è eseguito (N –2) – k +1 = N – k -1 volte si avrà:
C(for interno) = (N – k-1) • 12
Dunque la complessità del for interno dipende dal valore dell’indice k.
Esempio (segue)
Quindi il costo complessivo dell’algoritmo sarà dato da:
C(bubblesort) = Σ (12N-12k-12) = 12N(N-1) – 12(1+2+…+N-2)-12(N-1)=
=12N2-12N –12(N-1)(N-2))/2 -12N-12=
= 12N2-12N-6(N2-2N-N+2)-12N-12=6N2-6N
Esercizio (segue)
Calcolare il costo dell’algoritmo di insertion sort ed il costo dell’algoritmo di selection sort.
Verificare che anche essi hanno un costo proporzionale al quadrato del numero di elementi degli array.
Le lezioni del Corso
1. Prime nozioni di Programmazione
2. C++ elementi di un programma
3. Le istruzioni di I/O standard
5. C++ funzioni matematiche ed espressioni booleane
6. Le strutture di controllo - parte seconda
8. Array di caratteri e tipi astratti
9. Astrazione procedurale: Procedure e Funzioni
10. Astrazione procedurale: Procedure e Funzioni -parte seconda
11. Astrazione procedurale: Procedure e Funzioni - parte terza
12. Librerie
13. Le strutture di controllo - parte terza
14. Algoritmi
16. I File di testo
17. La classe string
