Come determinare l'altezza di un albero di ricorsione da una relazione di ricorrenza?

Question

Come si fa a determinare l'altezza di un albero di ricorsione, costruito quando si ha a che fare con i tempi di ricorrenza delle ricorrenze? In che cosa differisce dal determinare l'altezza di un albero normale?

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

edit: scusa, volevo dire aggiungere come ottenere l'altezza del albero di ricorsione dalla recidiva relazione.

Answer 1

L'altezza dell'albero di ricorsione dipende dall'algoritmo ricorsivo in questione. Non tutti gli algoritmi di divisione e conquista hanno alberi di altezza uniformi, così come non tutte le strutture ad albero hanno altezze uniformi. Se non è possibile determinare l'altezza massima possibile dell'algoritmo o se è necessario calcolare l'altezza effettiva dell'albero in fase di esecuzione, è possibile utilizzare una variabile globale per la funzione ricorsiva, incrementarla all'entrata della funzione e decrementare questo all'uscita della funzione. Questa variabile indicherà il livello corrente della procedura ricorsiva. Se necessario, è possibile mantenere il valore massimo di questa variabile in una seconda variabile.

Answer 2

In primo luogo, se si tratta di una domanda a casa, contrassegnarla come tale. Le immagini che linki implicano che sei in CS 455, con il Professor Wisman. :)

Il suggerimento principale che darò è questo: l'altezza dell'albero è ovviamente determinata da quando si arriva alle "foglie". Le foglie di un albero che modellano la relazione di ricorrenza di una funzione sono il caso base. Quindi, guarderei per vedere come "rapidamente" N può ridursi al caso base.

Answer 3

Se la ricorrenza è in forma di T (n) = aT (n/b) + f (n), la profondità dell'albero è log base b di n.

Ad esempio, 2T (n/2) + n ricorrenza avrebbe l'albero di profondità lg (n) (base di registro 2 di n).