Albero di ricorsione (Struttura dati)

Definizione di albero di ricorsione

Un albero di ricorsione è una rappresentazione grafica del processo di un algoritmo ricorsivo e del costo associato ad ogni sua invocazione. È un metodo potente per visualizzare e analizzare le ricorrenze, in particolare per quelle della forma , dove:

• è il tempo di esecuzione per un problema di dimensione .
• è il numero di sottoproblemi generati da ciascuna chiamata ricorsiva.
• è la dimensione di ciascun sottoproblema.
• rappresenta il costo delle operazioni non ricorsive: la fase di “Divide” (suddivisione del problema) e la fase di “Combina” (unione delle soluzioni dei sottoproblemi).
• Il caso base per sufficientemente piccolo (spesso ) funge da condizione di arresto della ricorsione.

Struttura dell’albero

In un albero di ricorsione:

1. Ogni nodo contiene il costo per la risoluzione di un singolo sottoproblema ricorsivo in quel punto dell’esecuzione.
2. La radice rappresenta il problema originale di dimensione e il costo delle operazioni non ricorsive a quel livello.
3. I figli di un nodo corrispondono ai sottoproblemi in cui il problema del nodo padre viene suddiviso. Il numero di figli è , e la dimensione dei sottoproblemi è .
4. L’albero si estende verso il basso fino a raggiungere i nodi foglia, che rappresentano i casi base della ricorsione (problemi di dimensione sufficientemente piccola da essere risolti in tempo costante ).

Analisi della complessità tramite albero di ricorsione

L’obiettivo dell’analisi con un albero di ricorsione è sommare i costi di tutti i nodi per ottenere il costo totale dell’algoritmo. Questo si fa tipicamente calcolando il costo totale di ogni livello dell’albero e poi sommando i costi di tutti i livelli.

Passi per l’analisi:

1. Determinare l’altezza dell’albero (numero di livelli): Per una ricorrenza , l’altezza di un albero ricorsivo bilanciato è data da (escludendo il livello delle foglie). Questo rappresenta il numero di volte che l’input viene diviso per fino a raggiungere la dimensione del caso base.
2. Calcolare il costo per ogni livello: A ogni livello (partendo da per la radice), il costo totale è dato dal numero di nodi a quel livello moltiplicato per il costo di ciascun nodo a quel livello.
3. Calcolare il numero di foglie: Il numero di nodi al livello più profondo (le foglie) è . Il costo totale delle foglie è questo numero moltiplicato per .
4. Sommare i costi di tutti i livelli: Il tempo di esecuzione complessivo è la somma dei costi di tutti i livelli, inclusi i costi dei nodi foglia. Questa somma può spesso essere espressa come una serie geometrica o un’altra forma chiusa.

Esempio Pratico:

Consideriamo la ricorrenza . Qui abbiamo:

• (ogni problema si suddivide in 3 sottoproblemi).
• (la dimensione di ciascun sottoproblema è ).
• (il costo delle operazioni non ricorsive a ogni livello).

Visualizziamo l’albero di ricorsione:

• Livello 0 (Radice):

  • Problema di dimensione .
  • Costo: .

• Livello 1:

  • Vengono generati sottoproblemi, ciascuno di dimensione .
  • Costo per ogni sottoproblema: .
  • Costo totale del livello: .

• Livello 2:

  • Vengono generati sottoproblemi, ciascuno di dimensione .
  • Costo per ogni sottoproblema: .
  • Costo totale del livello: .

• Livello (generico):

  • Vengono generati sottoproblemi, ciascuno di dimensione .
  • Costo totale del livello: .

• Altezza dell’albero: L’altezza è . L’albero ha livelli (dalla radice al livello prima delle foglie).

• Costo totale (somma dei livelli): Il costo totale dell’algoritmo è la somma dei costi di ogni livello, più il costo dei nodi foglia. La somma dei costi dai livelli a (escluse le foglie) è: . Questa è una serie geometrica con ragione . Poiché , la serie converge a . Quindi la somma dei costi dei livelli superiori è .

• Costo dei nodi foglia: Il numero di nodi foglia è . Poiché , il costo delle foglie, , è asintoticamente inferiore al costo dei livelli superiori.

• Conclusione: Il costo dominante è quello della radice e dei livelli più vicini ad essa, che sommano a . Pertanto, la soluzione asintotica della ricorrenza è .

Relazione con altri Metodi di Risoluzione

L’albero di ricorsione è un metodo grafico che fornisce un’intuizione chiara sul comportamento della ricorrenza. Spesso, l’intuizione ottenuta dall’albero di ricorsione può essere usata per formulare un’ipotesi nel metodo di sostituzione, che richiede una dimostrazione formale per induzione matematica. Per ricorrenze di forma standard, il Master Theorem (o Metodo Principale) offre una soluzione più rapida, classificando le ricorrenze in base al confronto tra e la funzione “spartiacque” . L’albero di ricorsione aiuta a comprendere perché il Master Theorem funziona, mostrando visivamente il contributo relativo della radice, dei livelli intermedi e delle foglie al costo totale.