Esercizi svolti di informatica n.3

Dato un array A di n interi scrivere una funzione C che, usando il paradigma del “divide et impera” restituisce il massimo ed il minimo di A in tempo O(n). Verificare tale complessità tramite l’impostazione e la risoluzione di un’equazione di ricorrenza.

SOLUZIONE.

Cominciamo col fare qualche osservazione: il metodo del “divide et impera”, incontrato spesso in molti algoritmi noti (ad esempio nel Merge Sort) si basa sull’idea di ridurre il problema dato, di dimensione n, a due o più problemi di dimensione inferiore; per sua natura è quindi un metodo basato sulla ricorsione. L’idea di produrre un algoritmo ricorsivo dovrebbe essere anche suggerita dal fatto che si chiede di calcolare la complessità tramite equazione di ricorrenza.

L’unica scelta che si deve fare è dunque quella di decidere come suddividere il problema in due sottoproblemi. Le uniche possibilità sensate sono le seguenti:

1. calcolare ricorsivamente il massimo ed il minimo nei due sottovettori destro e sinistro di dimensione n/2, confrontare poi i due massimi ed i due minimi dando in output il massimo e minimo globali;
2. calcolare ricorsivamente il massimo ed il minimo del sottovettore di dimensione n-1 ottenuto eliminando il primo (o l’ultimo) elemento, confrontare poi il massimo ed il minimo ottenuti con l’elemento eliminato dando in output il massimo e minimo globali.

Per comprendere quale dei due approcci sia migliore, proviamo a calcolarne la complessità.


Per quanto riguarda il primo metodo, il tempo di esecuzione su un input di n elementi T(n) è pari al tempo di esecuzione dello stesso algoritmo su ciascuno dei due sottovettori di n/2elementi, più il tempo necessario per confrontare i due massimi ed i due minimi; il caso base si ha quando i sottovettori sono di dimensione 1, per cui il massimo ed il minimo coincidono, e l’unica operazione da fare è quella di confrontare tra loro massimi e minimi per dare in output i valori globali. L’equazione di ricorrenza è dunque:

T(n)=2T(n/2)+(1)

T(1)=(1)

Risolvendo questa equazione con il metodo iterativo (ma si può fare anche con il metodo dell’albero), si ottiene T(n)=2²T(n/2²)+(1)+(1)=2³T(n/2³)+(1)+(1)+(1)=…=2^k+T(n/2^k)+k(1).

Procediamo fino a quando n/2^knon sia uguale ad 1 e cioè fino a quando k=log n. In tal caso, sostituendo nell’espressione di T(n) e sfruttando il caso base si ha: T(n)=n+(1)+log n (1)=(n).

Studiamo ora il secondo approccio: il tempo di esecuzione dell’algoritmo du un input di n elementi, T(n)è pari al tempo di esecuzione dello stesso algoritmo su n-1elementi più il tempo per confrontare l’elemento eliminato con il massimo ed il minimo trovati; anche qui il passo base si ha quando n=1 e cioè quando massimo e minimo coincidono. L’equazione di ricorrenza allora diventa:

T(n)=T(n-1)+(1)

T(1)=(1)

Anche questa equazione si può risolvere con il metodo iterativo ottenendo T(n)=T(n-1)+(1)=T(n-2)+(1)+(1)=…T(n-k)+k(1).

Procediamo fino a quando n-k=1 cioè fino a quando k=n-1 e sostituiamo nell’equazione: T(n)=T(1)+(n-1)(1)=(n)se si tiene conto del caso base.

Deduciamo dai precedenti ragionamenti che entrambi i metodi sono ugualmente corretti ed efficienti, pertanto si può procedere (solo ora!) all’implementazione in C, che è lasciata al lettore.