Il problema viene suddiviso in sottoproblemi analoghi, che vengono risolti separatamente.
Le soluzioni dei sottoproblemi vengono infine fuse insieme per ottenere la soluzione dei problemi più complessi.
Consiste di 3 passi:
Merge Sort (divide et impera)
Algoritmo:
MergeSort(array A, int p,r)
1 if p < r then
2 q =
[Divide
]
3 MergeSort(A,p,q)
[Impera
]
4 MergeSort(A,q+1,r)
[Impera
]
5 Merge(A,p,q,r)
[Fondi
]
La funzione Merge(A,p,q,r) fonde le sue sottosequenze ordinate (una tra p e q e l’altra tra q+1 e r) in un’unica sequenza ordinata tra p e r. Al fine di mantenere il suo tempo di esecuzione lineare (), utilizza un array di appoggio B (locale) per effettuare gli spostamenti necessari.
L’algoritmo di Merge ha tempo di esecuzione lineare sulla lunghezza n delle sequenza da p a r:
L’analisi del tempo di esecuzione di un algoritmo ricorsivo si riduce spesso alla soluzione di una equazione di ricorrenza, che definisce implicitamente (ricorsivamente) la funzione di tempo
La forma di una equazione di ricorrenza è immediatamente riconducibile alla struttura dell’algoritmo cui è associata
Ad esempio, detto n il numero di elementi tra p e r, MergeSort viene chiamato ricorsivamente su due sottosequenza di dimensione
Se T(n) denota il tempo quando l’input ha dimensione n, denota il tempo quando l’input ha dimensione
MergeSort(array A, int p,r)
1 if p < r the
n
2 q =
3 MergeSort(A,p,q)
4 MergeSort(A,q+1,r)
5 Merge(A,p,q,r)
Sommando i termini associati alle linee dell’algoritmo, otterremo dunque l’equazione di ricorrenza che definisce il tempo di esecuzione di MergeSort:
La soluzione di un’equazione di ricorrenza può essere calcolata in modo molto semplice con l’ausilio di una rappresentazione grafica.
L’idea di base è quella di rappresentare le chiamate ricorsive come nodi dell’albero delle chiamate ricorsive, tra loro collegati in modo che una chiamata che genera una o più chiamate ricorsive risulti essere, nell’albero, padre dei nodi associati a tali chiamate.
È poi necessario associare ad ogni nodo il numero di operazioni elementari eseguite localmente alla chiamata ricorosiva associata (cioè le operazioni che non coinvolgono altre chiamate ricorsive)
Infine, è necessario sommare tra di loro i contributi associati a tutti i nodi dell’albero, ottenendo in tal modo una sommatoria di termini, come nel caso di algoritmi iterativi, la cui forma chiusa rappresenta la funzione del tempo di esecuzione.
Di seguito vediamo i passi relativi alla seguente equazione di ricorrenza:
La soluzione di un’equazione di ricorrenza può essere calcolata in modo molto semplice con l’ausilio di una rappresentazione grafica.
L’idea di base è quella di rappresentare le chiamate ricorsive come nodi di un albero, tra loro collegati in modo che una chiamata che genera una o più chiamate ricorsive risulti essere, nell’albero, padre dei nodi associati a tali chiamate.
È poi necessario associare ad ogni nodo il numero di operazioni elementari eseguite localmente alla chiamata ricorosiva associata (cioè le operazioni che non coinvolgono chiamate ricorsive)
Infine è necessario sommare tra di loro i contributi associati a tutti i nodi dell’albero, ottenendo in tal modo una sommatoria di termini, come nel caso di algoritmi iterativi, la cui forma chiusa rappresenta la funzione del tempo di esecuzione.
La figura a destra rappresenta il nodo radice associato alla prima chiamata con input n, con il contributo locale associato e i due nodi relativi alle chiamate ricorsive su input .
La figura a destra rappresenta il nodo radice associato alla prima chiamata con input n, con il contributo locale associato, i due nodi realtivi alle chiamate ricorsive su input con i contributi associati.
Ciascuno dei due figli della radice avrà poi due nodi figli, associati alle due chiamate ricorsive, ciascuna su input di dimensione la metà di quello ricevuto in ingresso dal padre, cioè .
Si noti che l’espressione associata ai nodi rappresenta il numero di operazioni elementari eseguite localmente dalla chiamata. Qundi, poiché l’equazione di ricorrenza associa operazioni quando l’input ha dimensione n, essa associerè operazioni quando l’input ha dimensione .
Una volta individuato l’albero di ricorrenza e i contributi dei nodi, il tempo di esecuzione può essere calcolato sommando tutti questi conrtibuti.
- nel caso in esame, l’albero è un albero binario pieno, cioè un albero in cui tutte le foglie sono alla stessa profondità e i nodi interni hanno grado 2.
Molto spesso risulta più semplice sommarli livello per livello e individuare, ove possibile, il termine generale del livello:
- nel caso in esame, i contributi dei nodi di ciascun livello sommano sempre a n.
Calcoliamo l’altezza dell’albero, cioè il numero di livelli (o chiamate ricorsive annidate) necessario affinché l’input divenga uguale a quello del caso base dell’equazione:
Infine, sommiamo il contributo dei livelli su tutti i livelli individuati, in altre parole: .
La slide successiva illustra il procedimento qui descritto.
Albero per l'equazione di ricorrenza dell'esempio, a sinistra è riportata l'altezza dell'albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.
A titolo di esempio, consideriamo la seguente equazione di ricorrenza:
Il termine corrisponde a quattro chiamate ricorsive, ciascuna eseguita su metà dell’input della chiamata padre.
Anche in questo caso, l’albero di ricorrenza risulterà pieno, ma di grado 4
Ogni nodo avrà contributo pari alla dimensione dell’input
Il livello i-esimo avrà contributo pari a
L’altezza dell’albero è, ancora una volta, pari a
La slide successiva riporta la soluzione dell’equazione di ricorrenza.
Albero per l'equazione di ricorrenza dell'esempio, a sinistra è riportata l'altezza dell'albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.
A titolo di esempio, consideriamo la seguente equazione di ricorrenza:
Il termine corrisponde a quattro chiamate ricorsive, ciascuna eseguita su due terzi dell’input della chiamata padre.
Anche in questo caso, l’albero di ricorrenza risulterà pieno e di grado 4
Ogni nodo avrà contributo pari al quadrato della dimensione dell’input
Il livello i-esimo avrà contributo pari a
L’altezza dell’albero si ottiene come soluzione di ed è pari a
La slide successiva riporta la soluzione dell’equazione di ricorrenza.
Albero per l'equazione di ricorrenza dell'esempio, a sinistra è riportata l'altezza dell'albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.
L’altezza dell’albero si ottiene come soluzione di ed è pari a
Di seguito sono riportati i calcoli della relativa sommatoria:
A titolo di esempio, consideriamo la seguente equazione di ricorrenza:
Il termine corrisponde a quattro chiamate ricorsive, ciascuna eseguita su due terzi dell’input della chiamata padre.
In questo caso, l’albero di ricorrenza risulterà un albero binario non pieno.
Ogni nodo avrà contributo pari alla dimensione dell’input
Il livello i-esimo avrà contributo pari a
Poichè l’albero non è pieno, non è facile calcolare con precisione la somma dei contributi dei nodi
Per effettuare l’analisi, procederemo per apprissimazioni, calcolando un’approssimazione per difetto e una per eccesso della somma dei contributi.
Per l’approssimazione per difetto calcoleremo la somma dei contributi dei nodi del più grande albero pieno contenuto nell’albero di ricorrenza dell’equazione:
la cui soluzione è
Calcoliamo quindi la funzione:
che rappresenta un limite inferiore asintotico per .
Per l’approssimazione per eccesso calcoleremo la somma dei contributi dei nodi del più piccolo albero pieno che contiene l’albero di ricorrenza dell’equazione:
la cui soluzione è
Calcoliamo quindi la funzione:
che rappresenta un limite superiore asintotico per .
Albero per l'equazione di ricorrenza non pieno dell'esempio. Le due approssimazioni, per difetto e per eccesso, in questo caso coincidono asintoticamente, perciò possiamo concludere T(n)=θ(n)
È possibile analizzare il tempo di esecuzione di un algoritmo ricorsivo, risolvendo un’equazione di ricorrenza.
L’equazione di ricorrenza definisce la regola di generazione dell’albero delle chiamate ricorsive dell’algoritmo.
Per risolvere l’equazione di ricorrenza, è sufficiente sommare i contributi locali, in termini di operazioni elementari, di ciascuna chiamata ricorsiva.
Un modo semplice è quello di calcolare il termine generale corrispondente alla somma dei contributi dei nodi che risiedono nello stesso livello i-esimo.
Se l’albero generato dalla ricorrenza è pieno, allora, nota l’altezza dell’albero, è sufficiente calcolare la somma, su tutti i livelli, dei termine generale.
In caso l’albero non sia pieno, si possono individuare un limite inferiore asintotico e un limite superiore asintotico, tramite il calcolo di un’approssimazione per difetto e una per eccesso, rispettivamente.