Algoritmi e Strutture Dati
Il problema della ricerca
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esercizio di approfondimento da
correggere
Sia dato un mazzo di n carte scelte in un universo
U di 2n carte distinte, e si supponga di dover
verificare se una certa carta xU appartenga o
meno al mazzo. Progettare un algoritmo per
risolvere tale problema, e analizzarne il costo (in
termine di numero di confronti) nel caso migliore,
peggiore e medio.
2
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Algoritmo di ricerca sequenziale
Un primo algoritmo è quello di ricerca sequenziale (o
esaustiva), che gestisce il mazzo di carte come una lista L
non ordinata
Contiamo il numero di confronti (operazione dominante):
Tbest(n) = 1
x è in prima posizione
Tworst(n) = n
xL oppure è in ultima posizione
Tavg(n) = P[xL]·n + P[xL e sia in prima posizione]·1 + P[xL
e sia in seconda posizione]·2 +… + P[xL e sia in n-esima
posizione]·n
3
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Nel caso del mazzo di carte…
• Assumendo che le istanze siano equidistribuite, la probabilità
che una carta appartenga (o non appartenga) al mazzo è ½, e la
probabilità che l’elemento appartenga al mazzo e sia in posizione
i-esima è ½·1/n
 Tavg(n) = ½·n + ½·1/n·1 + ½·1/n·2 +…+ ½·1/n·n =
= ½·n + ½·1/n·[1+2+…+n] = ½·n + ½· 1/n ·[n ·(n+1)/2] =
(3n+1)/4
 Tavg(n) = Tworst(n) = Θ(n)
• L’analisi del caso medio può rivelarsi molto complicata…
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Algoritmo di ricerca binaria
Se ipotizzassimo che il mazzo di carte fosse una lista L
ordinata, potremmo progettare un algoritmo più efficiente:
Confronta x con l’elemento centrale di L e prosegue nella
metà sinistra o destra in base all’esito del confronto
Approfondimento: dimostrare formalmente la
correttezza dell’algoritmo.
5
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempi su un array di 9 elementi
Cerca 2
Cerca 1
Cerca 9
Cerca 3
3<4 quindi a e b
si invertono
6
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Analisi dell’algoritmo di ricerca binaria
Contiamo i confronti eseguiti nell’istruzione 3 (operazione dominante):
Tbest(n) = 1
l’elemento centrale è uguale a x
Tworst(n) = Θ(log n) xL
Infatti, poiché la dimensione del sotto-array su cui si procede
si dimezza dopo ogni confronto, dopo l’i-esimo confronto il
sottoarray di interesse ha dimensione n/2i. Quindi, dopo
i=log n +1 confronti, si arriva ad avere a>b.
Tavg(n) = P[xL]· (log n +1 )+ P[xL e sia in posizione centrale]·1
+P[xL e sia in posizione centrale nelle 2 sottometà]·2+
+P[xL e sia in posizione centrale nelle 4 sotto-sottometà]·3 + …+
+P[xL e sia in una delle 2 log n  n/2 posizioni raggiungibili con a=b]· (log n +1 )
4
7
3
4
2
4
3
4
1
4
3
4
2
4
3
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Nel caso del mazzo di carte…
Se il mazzo di carte ci venisse dato ordinato, applicando la
ricerca binaria avremmo:

Tavg(n) = ½·(log n +1) + ½·1/n·1 + ½·2/n·2 + ½·4/n·3 + …
+ ½·(n/2)/n·(log n +1 )
quindi, se xL, in circa metà dei casi pago (log n +1 ), e nell’altra
metà dei casi pago un valore minore di (log n +1 )
 Tavg(n) < ½·(log n +1) + ½·(log n +1) = log n +1
e poiché Tavg(n) > 1/2· log n, ne consegue che Tavg(n) =Θ(log n)
 Tavg(n) = Tworst(n) = Θ(log n)
8
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Analisi di algoritmi ricorsivi
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Ricerca binaria in forma ricorsiva
L’algoritmo di ricerca binaria può essere riscritto
ricorsivamente come:
Come analizzarlo?
10
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Equazioni di ricorrenza
Il tempo di esecuzione dell’algoritmo può essere
descritto tramite l’equazione di ricorrenza:
T(n) ≤
Θ(1) + T((n-1)/2) se n≥1
Θ(1)
se n=0
dove Θ(1) è il costo (costante) che viene speso
all’interno di ogni chiamata ricorsiva.
Mostreremo due metodi per risolvere equazioni di
ricorrenza: iterazione e teorema Master
11
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Metodo dell’iterazione
Idea: “srotolare” la ricorsione, ottenendo una
sommatoria dipendente solo dalla dimensione n del
problema iniziale (già visto per Fibonacci6)
Nel caso della ricerca binaria: T(n) ≤ Θ(1) + T(n/2)
T(n/2) ≤ Θ(1) + T(n/4)
...
T(n) ≤ Θ(1) + T(n/2) ≤ 2·Θ(1)+ T(n/4) ≤ …
≤ ( ∑j=1...i Θ(1)) + T(n/2i) = i ·Θ(1) + T(n/2i)
Per i=log2n: T(n) ≤ Θ(1)·log n + T(1) = Θ(log n)
12
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esercizi di approfondimento
Risolvere usando il metodo dell’iterazione le
seguenti equazioni di ricorrenza:
• T(n) = n + T(n-1), T(1)=1;
• T(n) = 9 T(n/3) + n, T(1)=1;
(soluzione sul libro di testo: Esempio 2.4)
13
Copyright © 2004 - The McGraw - Hill Companies, srl
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 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) =
14
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
Algoritmo di ricerca binaria
a=1, b=2, f(n)=Θ(1)
15
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)
16
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempi
1) T(n) = n + 2T(n/2)
a=2, b=2, f(n)=n=Q(n log22 )
(caso 2 del teorema master)
T(n)=Q(n log n)
2) T(n) = 7 + 3T(n/9)
a=3, b=9, f(n)=7=O(n log93 - e )
(caso 1 del teorema master)
T(n)=Q(√n)
3) T(n) = n + 3T(n/9)
a=3, b=9, f(n)=n=W(n log93 + e)
inoltre 3(n/9)≤ c n per c=1/3
(caso 3 del teorema master)
17
T(n)=Q(n)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempi
4) T(n) = n log n + 2T(n/2)
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!
18
Copyright © 2004 - The McGraw - Hill Companies, srl