Post on 22-Feb-2019
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Tempo e spazio di calcolo
Modelli di calcolo e metodologie di analisi
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
In quale modo stimiamo il tempo di calcolo?
• Approccio empirico (a posteriori)
• Approccio teorico (a priori)
Possiamo considerare due approcci:
SECONDO VOI QUALE STUDIEREMO IN QUESTO CORSO ?
SECONDO VOI QUALE E’ IL PIU’ UTILE IN PRATICA ?
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Sviluppiamo una metodologia per l’approccio teorico
Per sviluppare la metodologia per stimare il tempo e lo spazio di calcolo dobbiamo precisare:
1. Linguaggio per descrivere gli algoritmi2. Modello computazionale d’esecuzione3. Metrica per misurare il tempo di calcolo4. Modo per caratterizzare il tempo di calcolo
per gli algoritmi ricorsivi
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Pseudo-codice Java-like:
assegnazione: ←i ← j ← k equivale alla seq.: j ← k; i ← j
espressioni: simboli matematici standard per espressioninumeriche e booleane
commento:
dichiarazione di metodo: nome (param 1, param 2, ...)
chiamata di un metodo: nome (param 1, param 2, ...)
ritorno da un metodo: return valore
1. Linguaggio per descrivere gli algoritmi
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
• dati composti: • i-esimo elemento array A: A[i]• A[i . . j] ≡ <A[i], A[i+1], . . . , A[j]>, se i ≤ j
sequenza vuota, se i > j• i dati composti sono organizzati in oggetti, che
sono strutturati in attributi o campi: ad es. length[A] • una variabile che rappresenta un oggetto è un riferimento
• un riferimento che non si riferisce a nessun oggetto: nil
• parametri alle procedure passati per valore (per gli oggetti una
copia del riferimento)
Pseudo-codice Java-like (continua):
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
• struttura di blocco: spaziatura
• costrutti iterativi e condizionali :
if condizione then azioni (else azioni)
while condizione doazioni
do azioni while condizione
for variabile ← val-iniz. to val-fin. (incremento) doazioni
for variabile ← val-iniz. downto val-fin. (decremento) doazioni
Pseudo-codice Java-like (continua):
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
2. Il modello computazionale d’esecuzione
1. assegnazione di un valore ad una variabile2. chiamata di un metodo3. eseguire un’operazione aritmetica4. confronto di due numeri5. indicizzazione di un elemento in un array6. riferimento a un oggetto7. rientro da un metodo
Consideriamo come operazioni primitive le seguenti operazioni :
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
• Questo approccio dà origine al modello computazionale chiamato Random Access Machine (RAM):
• CPU connessa a un banco di celle di memoria• ogni cella memorizza una parola (un numero, un carattere, . . .
In generale: il valore di un tipo di base o un riferimento ad un oggetto)
• la CPU accede ad una cella di memoria arbitraria con unaoperazione primitiva (ogni operando e’ una cella di memoria)
Assunzione implicita: il numero di operazioni primitive è proporzionale al tempo di esecuzione dell’algoritmo
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
La quantità di tempo (e di spazio) consumato dall’esecuzione di un programma RAM su un dato input può essere determinato essenzialmente usando due criteri:
Criterio di costo uniforme:l’esecuzione di un’istruzione primitiva richiede un tempo indipendente dalla “grandezza” degli operandi (ricordate: un operando e’ o un valori di un tipo base o un riferimentoad un oggetto)
Criterio di costo logaritmico:il tempo di calcolo richiesto da un’istruzione primitiva dipende dal numero di bit necessari a rappresentare gli operandi
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Misureremo il tempo di calcolo contando le operazioni primitive
Massimo (A, n)current-max ← A[0]for i ← 1 to n-1 do
if current-max < A[i]then current-max ← A[i]
return current-max
21 + n
1
4*(n-1)…6 *(n-1)
Numero di operazioni primitive: t (n) = minimo 2 + 1 + n + 4*(n-1) + 1 = 5*nmassimo 2 + 1 + n + 6*(n-1) + 1 = 7*n - 2
3. Metrica per misurare il tempo di calcolo
Ad esempio:
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
istanze in input
tempo di calcolo
5 ms
3 ms
1 ms
A B C D E F G
tempo nel caso peggiore
tempo nel caso migliore
In generale, istanze diverse avranno tempi di calcolo diversi, ad esempio:
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Analisi del caso medioIl tempo di calcolo medio dell’algoritmo definito come media dei tempi per tutti i possibili input
Per poterlo calcolare si deve conoscere la distribuzione di probabilità sull’insieme dei possibili inputIn generale si tratta di un compito non banale. In mancanza di informazioni si puo’ assumere una distribuzione uniforme, ma si tratta di un’assunzione arbitraria!
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Analisi del caso peggiore• non richiede teoria probabilità• caso peggiore quasi sempre facile da identificare• se un algoritmo si “comporta bene” nel caso peggiore, si
“comporta bene” su ogni input (fornisce una garanzia!)
Analisi del caso ottimo• non richiede teoria probabilità• caso ottimo quasi sempre facile da identificare• se un algoritmo si comporta male nel caso ottimo, si
comporta male su ogni input
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Equazione di ricorrenza: una funzione che esprime il numero di operazioni sull’input di dimensione n in funzione delnumero di operazioni su input di dimensione inferiore.
Massimo-ricorsivo (A, n)if n = 1
then return A[0]return max (Massimo-ricorsivo (A, n-1), A[n-1])
T(n) = 3 se n = 1T(n-1) + k altrimenti
T(n) = k*(n-1) + 3
4. Modo per caratterizzare il tempo di calcolo degli algoritmi ricorsivi
Ad esempio: n > 1
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Moltiplicazione per “somme successive”
moltiplicazione (x1, x2)y ← x1prod ← 0while y > 0 do
prod ← prod + x2 y ← y - 1
return prod
45 1944 1943 19
4 19
1 19
855
. .. .. .
3 192 19
y x2
ESEMPIO: tempo di calcolo della moltiplicazione per somme successive
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Moltiplicazione “alla russa”
19
76
---
152---
608
855
45 1922 3811 765 1522 3041 608
y1 y2
prod ← 0while y1 > 0 do
if y1 is oddthen prod ← prod + y2
y1 ← y1 div 2y2 ← y2 + y2
return prod
molt-russa (x1, x2)y1 ← x1y2 ← x2
ESEMPIO: tempo di calcolo della moltiplicazione alla russa
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
prod ← 0while y1 > 0 do
if y1 is odd then prod ← prod + y2
y1 ← y1 div 2y2 ← y2 + y2
return prod
molt-russa (x1, x2)y1 ← x1y2 ← x2
moltiplicazione (x1, x2)y ← x1prod ← 0while y > 0 do
prod ← prod + x2 y ← y - 1
return prod
moltiplicazione molt-russa2 * x1 assegnazioni 3 * lg x1 assegnazioni
nel while x1 somme lg x1 divisionix1 decrementi 2 * lg x1 sommex1+1 confronti 2 * lg x1 + 1 confronti
5 * x1+1 + 3 operazioni 8 lg x1+1 + 4 operazioni
Moltiplicazione per somme successive vs moltiplicazione alla russa
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
4
34
39
44
49
54
29
24
19
14
9
31,5830,36
2927,46
25,6823,58
2117,68
13
5
0
10
20
30
40
50
60
0 1 2 3 4 5 6 7 8 9 10 11
moltiplicatore
num
ero
di o
pera
zion
i
f(m) = 5m + 4 g(m) = 8 lg m + 5
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Introduciamo un’ulteriore astrazione : tasso di crescita o ordine di grandezza
del tempo di calcolo
• ogni passo nello pseudo-codice (e ogni statement in un linguaggio ad alto livello) corrisponde a un piccolo numero di operazioni primitive che non dipendono dalla dimensione dell’input
• basta considerare il termine principale perchè i termini di ordine inferiore non sono significativi per n grande.
L’ordine di grandezza del tempo di calcolo fornisce una semplice caratterizzazione dell’efficienza e consente di confrontare algoritmi alternativi.
LA NOTAZIONE ASINTOTICA
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Notazione asintotica
Consideriamo funzioni dai naturali ai numeri reali non negativi
Efficienza asintotica degli algoritmi: come cresce il tempo diesecuzione con il crescere al limite della dimensione delle istanze in input
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Notazione O: O (g(n)) e’ l’insieme di tutte le funzioni f(n) percui esistono due costanti positive c ed n0 tali che
f(n) ≤ c • g(n) per tutti gli n ≥ n0
f(n) ∈ O (g(n))
n0
f(n)
c g(n)
n
tempo di run
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Notazione Ω: Ω(g(n)) e’ l’insieme di tutte le funzioni f(n) percui esistono due costanti positive c ed n0 tali che
f(n) ≥ c • g(n) per tutti gli n ≥ n0
f(n) ∈ Ω (g(n))
n0 n
f(n)
c g(n)tempo di run
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
f(n) ∈ Θ (g(n))
Notazione Θ: Θ(g(n)) e’ l’insieme di tutte le funzioni f(n) per cui esistono tre costanti positive c1, c2 ed n0 tali che
c1• g(n) ≤ f(n) ≤ c2 • g(n) per tutti gli n ≥ n0
c2 g(n)
n0
f(n)
n
c1 g(n)tempo di run
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Proprietà della notazione asintotica
Transitiva:f(n) = Θ (g(n)) e g(n) = Θ (h(n)) f(n) = Θ (h(n))f(n) = O (g(n)) e g(n) = O (h(n)) f(n) = O (h(n)) f(n) = Ω (g(n)) e g(n) = Ω (h(n)) f(n) = Ω (h(n))
Riflessiva: f(n) = Θ (f(n))f(n) = O (f(n))f(n) = Ω (f(n))
Simmetrica: f(n) = Θ (g(n)) g(n) = Θ (f(n))
Simmetrica trasposta: f(n) = O (g(n)) g(n) = Ω (f(n))
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
• d(n) = O(f(n))
a . d(n) = O(f(n)), per ogni costante a > 0
• d(n) = O(f(n)) & e(n) = O(g(n))
d(n) + e(n) = O(f(n) + g(n))
• d(n) = O(f(n)) & e(n) = O(g(n))
d(n) . e(n) = O(f(n) . g(n))
• f(n) funzione polinomiale di grado d:
f(n) = a0 + a1n + . . . + adnd f(n) = O(nd)
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
O(log n) logaritmica
O(n) lineare
O(n2) quadratica
O(nk) (k ≥ 1) polinomiale
O(an) (a > 1) esponenziale
Alcune classi di complessità
trattabili
non trattabili
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Alcune funzioni ordinate per velocità di crescita
n log n n n n log n n2 n2
2 1 1,41 2 2 4 8
4 2 2 4 8 16 64
8 3 2,83 8 24 64 512
16 4 4 16 64 256 4.096
32 5 5,66 32 160 1.024 32.768
64 6 8 64 384 4.096 262.144
128 7 11,31 128 896 16.384 2.097.152
256 8 16 256 2.048 65.536 16.777.216
512 9 22,63 512 4.608 262.144 134.217.728
1.024 10 32 1.024 10.240 1.048.576 1.073.741.824
2n
4
16
256
65.536
4.294.967.296
1,84 x 1019
3,40 x 1038
1,15 x 1077
1,34 x 10154
1,79 x 10308
n3
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
1
2
3
4
5
6
7
8
9
10
2
4,75
8
4
9
8
4
8
1,58
2,582,81
3,323,58
2,32
3,17
2
3
3,46
2,652,45
3,162,83
1,411,73
22,24
33,32 3,46
0
1
2
3
4
5
6
7
8
9
10
2 3 4 5 6 7 8 9 10 11 12
lognradnnn lognn^2n^32^n
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
0
10
20
30
40
50
60
2 3 4 5 6 7 8 9 10 11 12
lognradnnn lognn^2n^32^n
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
0
500
1000
1500
2000
2500
3000
3500
4000
4500
2 3 4 5 6 7 8 9 10 11 12
lognradnnn lognn^2n^32^n
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Problema: ordinamento di numeri.Input: una sequenza di n numeri <a1, a2,…,an>.Output: una permutazione <a1’, a2’,…,an’> della sequenza di
input tale che a1’≤ a2’ ≤ … ≤ an’.
ESEMPIO: tempo di calcolo dell’algoritmo di ordinamento per inserzione
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
3 5 1 8 2
key = 1
1 2 3 4 5
3 5 1 8 2
key = 5
1 2 3 4 5
1 3 5 8 2
key = 8
1 2 3 4 5
1 3 5 8 2
key = 2
1 2 3 4 5
3 5 5 8 2
1 3 5 8 2
1 3 5 8 8
1 2 3 5 8
1 3 5 5 8
3 3 5 8 2
1 3 3 5 8
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
num. volte1nn – 1
n – 1Σ tj ( j=2..n)Σ(tj – 1) ( j=2..n)Σ(tj – 1) ( j=2..n)n – 1n – 1
Insertion-sort (A) j ← 2
1 for j ← 2 to length[A] do2 key ← A[j]3 inserisci A[j] nella sequenza A[1. .j-1]
spostando a destra gli elementi > di A[j]
4 i ← j – 15 while i > 0 and A[i] > key do6 A[i+1] ← A[i]7 i ← i – 18 A[i+1] ← key
j ← j+1T(n) = 1 + a*n + b*(n-1) + c*Σ tj + d*Σ(tj – 1) =
= (a + b)*n + (1 – b) + c*Σ tj + d*Σ(tj – 1)
NON E’ UN INVARIANTE!
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Caso migliore: A è ordinato
T(n) è una funzione lineare di n.
T(n) è una funzione quadratica di n.
Caso peggiore: A è ordinato in ordine inverso
Caso medio (considerando ogni permutazione è ugualmente probabile)
T(n) è una funzione quadratica di n.
T(n) = 1 + a*n + b*(n – 1) + c*Σ tj + d*Σ(tj – 1) == (a + b) *n + (1 – b) + (c+d)* Σ tj – n + 1 == (a + b –1)*n + (2 – b) + (c+d)* Σ tj == e*n + f + g* Σ tj
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
ESEMPIO: il problema della valutazione di un polinomio
Input: una sequenza di n+1 numeri reali A = <a0, a1,…,an> e il valore della variabile xOutput: il valore del polinomio di grado n: P(x) = a0 + a1x+ … + anxn
Un algoritmo che risolve il problema:Poly-eval (A, x, n)1 y ← 12 result ← A[0]3 for i ← 1 to n do4 y ← y • x5 result ← result +A[i] • y y = xi6 return result
L’algoritmo esegue 2*n moltiplicazioni n somme e 2*n assegnazioni.Ma si può fare meglio
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
La regola di Horner:P(x) = a0 + x (a1+ … + x (an-1+ x an))…)
Un algoritmo basato sulla regola di Horner:Horner (A, x, n)1 result ← A[n]2 for i ← n - 1 downto 0 do3 result ← result • x + A[i]4 return result
L’algoritmo esegue n somme, n moltiplicazioni e n assegnazioni.
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
Horner (A, x, n)1 result ← A[n]2 for i ← n - 1 downto 0 do3 result ← result • x + A[i]4 return result
Poly-eval (A, x, n)1 y ← 12 result ← A[0]3 for i ← 1 to n do4 y ← y • x5 result ← result +A[i] • y6 return result
Poly-eval: 9*n + 6Horner: 7*n + 5
Poly-eval Horner5 4
n + 1 n + 18*n 6*n
fuori dal forconfrontinel for
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
15
915825
735645
555465
375285
195
105
1005
712642
572502
432362
292222
15212
82
782
0
200
400
600
800
1000
1200
1 11 21 31 41 51 61 71 81 91 101 111
T(n) = 9 n + 6
T(n) = 7 n + 5
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
L’algoritmo Horner è sicuramente migliore dell’algoritmo Poly-eval
L’analisi asintotica non distingue però tra i due algoritmi:per entrambi si ottiene Θ(n)
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
RIEPILOGO
• Una metodologia per l’approccio teorico alla stima del tempo di calcolo
• Analisi dei casi medio, peggiore, ottimo• Efficienza asintotica degli algoritmi• Risposta ad alcune domande lasciate in
sospeso durante le lezioni precedenti. • ESERCIZIO: Rispondete alle seguenti
domande. Quali domande restano ancora in sospeso? Adesso abbiamo gli strumenti per rispondere a qualcuna di esse? Se si, quali sono le risposte?
F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)
UN ALTRO ESERCIZIO
• La correttezza degli algoritmi considerati nei lucidi precedenti (o di loro minime varianti) e’ stata dimostrata (nelle lezioni precedenti) con il metodo delle asserzioni. ANNOTATE (SCRIVENDO SULLA STAMPA DEI LUCIDI) IL CODICE CON LE ASSERZIONI CHE NE DIMOSTRANO LA CORRETTEZZA. In questo modo vi sara’ piu’ facile seguire il ragionamento sulla loro complessita’!!!