Esercizi svolti di informatica n.6

Sia dato un albero binario completo con n nodi, radicato al nodo puntato dal puntatore r. Calcolare la complessità computazionale della seguente funzione, in funzione di n:


link Funzione(link r)
int fogliasx,fogliadx; link r1;
{
1. if (!r->fsin) && (!r->fdes)
2. return r
3. else {
4. r1=r;
5. while (r1->fsin) do
6. r1=r1->fsin;
7. fogliasx=r1->dato;
8. r1=r;
9. while (r1->fdes) do
10. r1=r1->fdes;
11. fogliadx=r1->dato;
12. if (fogliasx<fogliadx) return Funzione(r->fsin)
13. else return Funzione(r->fdes);
14.}
}

SOLUZIONE.

La funzione è ricorsiva e pertanto dobbiamo trovare un’equazione di ricorrenza in funzione di n; la complessità si ottiene sommando i contributi delle varie istruzioni:

• le linee 1. e 2. rappresentano il caso base, che costa (1);
• le linee 4., 7., 8. e 11. costano anch’esse (1);
• i cicli while delle linee 5. e 9. vengono ripetuti un certo numero di volte indefinto tra 1 e l’altezza dell’albero, infatti il primo ciclo si interrompe quando il nodo non ha figlio sinistro ed il secondo ciclo quando il nodo non ha figlio destro;
• le linee 12. e 13. sono chiamate ricorsive e quindi la loro complessità si dovrà scrivere come T() con un opportuno valore tra le parentesi, ma quale? Quanti nodi hanno i sottoalberi radicati ai figli sinistro e destro della radice? Possiamo dire che hanno k ed n-1-k nodi rispettivamente.

In totale otteniamo: T(n)=(1)+v₁(1)+v₂(1)+max(T(k), T(n-k)) dove v₁ e v₂sono il numero di volte in cui vengono ripetuti i cicli delle linee 5. e 9.. Arrivati qui, non sappiamo come procedere, se non sostituendo a v₁ e v₂l’altezza dell’albero, che ne è una limitazione superiore. Ma quanto vale l’altezza? un valore indefinito tra log n ed n, e questo significa che dobbiamo anche qui sostituire ad h la sua limitazione superiore n. Viste tutte queste approssimazioni che siamo costretti a fare, dovrebbe venire il dubbio di aver tralasciato qualcosa. Rileggendo con attenzione il testo, si osservi che l’albero in input è binario e COMPLETO. Questa ipotesi di cui non ci siamo interessati prima risolove numerosi problemi, infatti:

• tutti i nodi privi di figlio sinistro (ed anche di figlio destro) sono ad altezza log n, pertanto i due cicli alle linee 5. e 9. vengono ripetuti esattamente log n volte ciascuno;
• diventa facile calcolare max(T(k), T(n-k)): tanto il sottoalbero sinistro che quello destro contengono esattamente (n-1)/2 nodi ciascuno.

L’equazione di ricorrenza diventa allora:

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

T(1)=(1)

Risolvendo per iterazione si ha:

T(n)=(log n)+(log n/2)+ T(n/2²)=

=…=_i=0..k-1(log n/2ⁱ)+ T(n/2^k)=

=…(si procede fino a quando (n/2^k=1 e cioè fino a quando k=log n)…=

=_{i=0..log n-1} (log n/2ⁱ)+ T(n/2^{log n})=

=_{i=0..log n-1} (log n)- _{i=0..log n-1} (log 2ⁱ)+T(1)=

=(log ² n)-_{i=0..log n-1} i (log 2)+(1)=

=(log ² n)-(log 2)_{i=0..log n-1} i=

=(log ² n)-(log ² n) =(log ² n)