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 xU 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 xL oppure è in ultima posizione Tavg(n) = P[xL]·n + P[xL e sia in prima posizione]·1 + P[xL e sia in seconda posizione]·2 +… + P[xL 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 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) xL 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[xL]· (log n +1 )+ P[xL e sia in posizione centrale]·1 +P[xL e sia in posizione centrale nelle 2 sottometà]·2+ +P[xL e sia in posizione centrale nelle 4 sotto-sottometà]·3 + …+ +P[xL e sia in una delle 2 log n n/2 posizioni raggiungibili con a=b]· (log n +1 ) 7 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·(log n +1 ) < ½·(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