Algoritmi e Strutture Dati
Analisi di algoritmi ricorsivi:
Il Teorema master (*)
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Teorema Master
Permette di analizzare algoritmi basati sulla tecnica del
divide et impera:
- dividi il problema (di dimensione iniziale n) in a≥1
sottoproblemi di dimensione n/b, b>1
- risolvi i sottoproblemi ricorsivamente
- ricombina le soluzioni
Sia f(n) il tempo per dividere e ricombinare istanze di
dimensione n. La relazione di ricorrenza è data da:
T(n) =
2
a T(n/b) + f(n) se n>1
Θ(1)
se n=1
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio: algoritmo fibonacci6
a=1, b=2, f(n)=Θ(1)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio: algoritmo di ricerca
binaria
a=1, b=2, f(n)=Θ(1)
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Teorema Master
La relazione di ricorrenza:
T(n) =
a T(n/b) + f(n) se n>1
Θ(1)
se n=1
ha soluzione:
1. T(n) = Q(nlogba ) se f(n)=O(n logba- e) per qualche e>0
2. T(n) = Q(n logba log n) se f(n) = Q(n logba )
3. T(n) = Q(f(n)) se f(n)=W(n logba+ e ) per qualche e>0
(ma sotto l’ulteriore ipotesi che f(n) soddisfi la condizione di regolarità:
a f(n/b)≤ c f(n) per qualche c<1 ed n sufficientemente grande)
5
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Dimostrazione del caso 1
Albero della ricorsione
6
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Proprietà dell’albero della ricorsione
• Proprietà 1: il numero di nodi a livello i dell’albero della
ricorsione è ai (ricorda che la radice è a livello 0)
• Proprietà 2: i sottoproblemi a livello i dell’albero della
ricorsione hanno dimensione n/bi
• Proprietà 3: il contributo al tempo di esecuzione di un
nodo a livello i (escluso tempo chiamate ricorsive) è
f(n/bi)
• Proprietà 4: il numero di livelli dell’albero è (circa) logb n
logb n
i f(n/bi)
T(n)=
a
i=0
7
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
…quindi, nel caso 1
 logb a e  be logb n 1  1  
 logb a e  be ne  1  

   O n
 e
 
 O n
e



 b 1  
 b 1  


Inoltre, T(n) a logb n (ultimo termine della sommatoria)
= n logb a = Ω(n logb a ), da cui la tesi.
I casi 2 e 3 possono essere mostrati in modo analogo.
8
QED
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempi (per tutti assumiamo T(1)=Q(1))
1) T(n) = 2T(n/2) + n
a=2, b=2, f(n)=n=Q(n log22 )
T(n)=Q(n
log22
caso 2 TM
log n) = Q(n log n)
2) T(n) = 3T(n/9) + 7
a=3, b=9, f(n)=7=On log93 - e )
T(n) =Q(nlog93 )=Q(√n)
caso 1 TM
3) T(n) = 3T(n/9) + n
a=3, b=9, f(n)=n=W(n log93 + e)
inoltre 3(n/9)≤ c n per c=1/3
caso 3 del TM
T(n)=Q(n)
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempi
4) T(n) = 2T(n/2)+n log n
a=2, b=2 e quindi ovviamente non ricade nel caso 1 perché
f(n)=n log n ≠ O(n log22-e )  O(n 1-e)
inoltre f(n) ≠ Θ (n log22), e quindi non ricade nel caso 2,
infine non esiste alcun e > 0 per cui f(n)=W(nlog22+e)W(n1+e)
n log n
(infatti, limn n log
 e  0 per ogni e > 0 )
1 e
n
n
non si può applicare
il teorema Master!
10
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Upper e lower bound di un
algoritmo e di un problema
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Delimitazioni superiori (upper bound)
Definizione (complessità di un algoritmo)
Un algoritmo A ha costo di esecuzione O(g(n)) su istanze di
dimensione n e rispetto ad una certa risorsa di calcolo (spazio
o tempo), se la quantità f(n) di risorsa sufficiente per eseguire
A su qualunque istanza di dimensione n (e quindi in particolare
anche nel caso peggiore) verifica la relazione
f(n)=O(g(n)).
Definizione (upper bound di un problema)
Un problema P ha una delimitazione superiore alla
complessità O(g(n)) rispetto ad una certa risorsa di calcolo
(spazio o tempo) se esiste un algoritmo che risolve P il cui
costo di esecuzione rispetto a quella risorsa è O(g(n)).
12
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Delimitazioni inferiori (lower bound)
Definizione
Un algoritmo A ha costo di esecuzione W(g(n)) su istanze di
dimensione n e rispetto ad una certa risorsa di calcolo (spazio o tempo),
se la quantità f(n) di risorsa necessaria per eseguire A nel caso peggiore
(e quindi non è detto che debba essere necessaria per ogni istanza di
dimensione n: istanze facili potrebbero richiedere meno risorse!)
verifica la relazione
fworst(n)= W(g(n)).
Definizione (lower bound o complessità intrinseca di un problema)
Un problema P ha una delimitazione inferiore alla complessità
W(g(n)) rispetto ad una certa risorsa di calcolo (spazio o tempo) se
ogni algoritmo che risolve P ha costo di esecuzione W(g(n)) rispetto a
quella risorsa.
13
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Ottimalità di un algoritmo
Definizione
Dato un problema P con complessità intrinseca W(g(n))
rispetto ad una certa risorsa di calcolo (spazio o tempo), un
algoritmo che risolve P è ottimo (in termini di complessità
asintotica, ovvero a meno di costanti moltiplicative e di
termini additivi/sottrattivi di “magnitudine” inferiore) se ha
costo di esecuzione O(g(n)) rispetto a quella risorsa.
14
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Convenzioni
• Se scriverò che un algoritmo ha complessità T(n) =
O(g(n)), intenderò che su ALCUNE istanze costerà
Θ(g(n)), ma sulle rimanenti costerà o(g(n).
• Se scriverò che un algoritmo ha complessità
T(n)=Θ(g(n)), intenderò che su TUTTE le istanze
costerà Θ(g(n))
• Da ora in poi, quando parlerò di UB di un problema,
mi riferirò alla complessità del MIGLIORE
ALGORITMO che sono stato in grado di progettare
sino a quel momento (ovvero, quello con minore
complessità nel caso peggiore).
• Da ora in poi, quando parlerò di LB di un problema, mi
riferirò alla PIÙ GRANDE delimitazione inferiore che
sono stato in grado di dimostrare sino a quel momento.
15
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Alcuni esempi
• L’algoritmo di ricerca sequenziale di un elemento in un insieme
non ordinato di n elementi costa T(n) = O(n), in quanto su alcune
istanze costa Θ(n), mentre su altre costa o(n)
• Ovviamente, per quanto sopra, l’upper bound del problema della
ricerca di un elemento in un insieme non ordinato di n elementi è
pari a O(n)
• Si osservi ora che il lower bound del problema della ricerca di un
elemento in un insieme non ordinato di n elementi è pari a Ω(n):
infatti, ogni algoritmo di risoluzione deve per forza di cose
guardare tutti gli elementi dell’insieme per decidere se l’elemento
cercato appartiene o meno ad esso!
l’algoritmo di ricerca sequenziale è ottimo!
16
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Alcuni esempi (2)
• L’algoritmo Fibonacci4 per il calcolo dell’n-esimo numero
della sequenza di Fibonacci costa T(k=log n) = Θ(2k=n), in quanto
su tutte le istanze costa sempre Θ(2k=n)
• L’algoritmo Fibonacci6 per il calcolo dell’n-esimo numero
della sequenza di Fibonacci costa T(k=log n) = Θ(k=log n), in
quanto su tutte le istanze costa sempre Θ(k=log n)
• Ovviamente, per quanto sopra, l’upper bound del problema del
calcolo dell’n-esimo numero della sequenza di Fibonacci è pari a
O(log n)
• Si osservi ora che il lower bound del problema del calcolo dell’nesimo numero della sequenza di Fibonacci è pari a Ω(1): infatti,
ogni algoritmo di risoluzione deve per forza di cose leggere
l’input, al costo di 1 operazione, ma non sono in grado di definire
altre operazioni necessarie a tutti gli algoritmi!
l’algoritmo Fibonacci6 non è ottimo!
17
Copyright © 2004 - The McGraw - Hill Companies, srl