|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Capitolo 1 Un’introduzione informale
agli algoritmi Algoritmi e Strutture Dati
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Il tempo di esecuzione non è la sola risorsa di calcolo che ci interessa. Anche la quantità di memoria necessaria può essere cruciale.
Se abbiamo un algoritmo lento, dovremo solo attendere più a lungo per ottenere il risultato
Ma se un algoritmo richiede più spazio di quello a disposizione, non otterremo mai la soluzione, indipendentemente da quanto attendiamo!
E’ il caso di Fibonacci3, la cui correttezza è subordinata alla dimensione della memoria allocabile
Occupazione di memoria
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl fibonacci3 usa un array di dimensione n prefissata
In realtà non ci serve mantenere tutti i valori di Fn precedenti, ma solo gli ultimi due, riducendo lo spazio a poche variabili in tutto: Algoritmo fibonacci4 algoritmo fibonacci4(intero n) intero
a b 1
for i = 3 to n do
c a+b
a b b c
return b
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Per la risorsa tempo, calcoliamo il numero di linee di codice T(n) mandate in esecuzione
Se n≤2: tre sole linee di codice
Se n3: T(n) = 2+(n-1)+3·(n-2) = 4n-5 (per Fibonacci3 T(n)=2n)
Per la risorsa spazio, contiamo il numero di variabili di lavoro utilizzate: S(n)=4 (per Fibonacci3 S(n)=n+1) Correttezza? Corretto per definizione!
Efficienza?
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Misurare T(n) come il numero di linee di codice mandate in esecuzione è una misura molto approssimativa del tempo di esecuzione
Se andiamo a capo più spesso, aumenteranno le linee di codice sorgente, ma certo non il tempo richiesto dall’esecuzione del programma! Notazione asintotica
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Per lo stesso programma impaginato diversamente potremmo concludere ad esempio che T(n)=3n oppure T(n)=5n
Vorremmo un modo per descrivere l’ordine di grandezza di T(n) ignorando dettagli inessenziali come le costanti moltiplicative, additive e sottrattive
Useremo a questo scopo la notazione asintotica Θ
Notazione asintotica
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Supponiamo che
Allora, scriveremo che f(n) = Q(g(n)).
Notazione asintotica Q (definizione informale)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Esempi: Sia f(n) = 2n2 + 3n, allora f(n)=Θ(n2)
Sia f(n) = n3 -2n2+3n, allora f(n)=Θ(n3)
Sia f(n) = 23, allora f(n)=Θ(1)
Sia f(n) = 3n -2n, allora f(n)=Θ(3n)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Fibonacci2 T(n)=3Fn-2 T(n)=Θ(Fn) T(n)=Θ(n)
Fibonacci3 T(n)=2n T(n)=Θ(n)
Fibonacci4 T(n)= 4n-6 T(n)=Θ(n) Andamento asintotico per i Fibonacci
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Possiamo sperare di calcolare Fn in tempo inferiore a Θ(n)? Un nuovo algoritmo
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl fibonacci4 non è il miglior algoritmo possibile
E’ possibile dimostrare per induzione la seguente proprietà di matrici: Potenze ricorsive 1 1 1 0 n = Fn+1 Fn Fn Fn-1 Useremo questa proprietà per progettare un algoritmo più efficiente
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl …prodotto di matrici (AB)i,j= ai,k bk,j k=1 n i=1,…, n
j=1,…, n
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Dimostrazione per induzione Base induzione: n=2
1 1 1 0 2 = F3 F2 F2 F1 1 1 1 0 1 1 1 0 = 2 1 1 1 = Fn+1 Fn Fn Fn-1 Hp induttiva: 1 1 1 0 n-1 = Fn Fn-1 Fn-1 Fn-2 1 1 1 0 n = Fn Fn-1 Fn-1 Fn-2 1 1 1 0 Fn + Fn-1 Fn-1+ Fn-2 = = Fn Fn-1
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmo fibonacci5 Il tempo di esecuzione è T(n)=2+2(n-1)=Θ(n)
Possiamo migliorare?
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Possiamo calcolare la n-esima potenza elevando al quadrato la (└n/2┘)-esima potenza
Se n è dispari eseguiamo una ulteriore moltiplicazione
Esempio:
32=9 34 =(32)2= (9)2 =81 38=(34)2= (81)2 =6561 Calcolo di potenze
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmo fibonacci6
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Tutto il tempo è speso nella procedura potenzaDiMatrice
All’interno della procedura si spende tempo costante
Si esegue una chiamata ricorsiva con input n/2
L’equazione di ricorrenza è pertanto: Tempo di esecuzione T(n) = Θ(1) + T(n/2)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Metodo dell’iterazione Si può dimostrare che T(n) ≤ c log2 n + T(1) = Θ(log2 n )
Infatti: T(n)=T(n/2)+Θ(1)=[T(n/4)+Θ(1)]+Θ(1)=
=[{T(n/8)+Θ(1)}+Θ(1)] +Θ(1)=…
=((…(T(1)+Θ(1))+…+Θ(1))+Θ(1))+Θ(1)=Θ(log n) fibonacci6 è quindi esponenzialmente più veloce di fibonacci5!
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl Riepilogo fibonacci6 fibonacci5 fibonacci4 fibonacci3 fibonacci2 Θ(log n) Θ(n) Θ(n) Θ(n) Θ(n) Θ(log n) Θ(1) Θ(1) Θ(n) Θ(n) Tempo di esecuzione Occupazione di memoria fibonacci1 Θ(1) Θ(1)
|
|
|
|
|
|
Comments