Wie wird man die Höhe eines Rekursionsbaums bestimmen, der bei wiederkehrenden Laufzeiten erstellt wird? Wie unterscheidet es sich von der Höhe eines normalen Baumes?
alt text http://homepages.ius.edu/rwisman/C455 /html/notes/Chapter4/ch4-9.gif
edit: Entschuldigung, ich wollte hinzufügen, wie die Höhe des Rekursionsbaums aus der Rekursionsbeziehung erhalten wird.
Wenn es sich um eine Hausaufgabenfrage handelt, markieren Sie sie bitte als solche. Die Bilder, auf die Sie verlinken, deuten darauf hin, dass Sie in CS 455 bei Professor Wisman sind. :)
Der wichtigste Hinweis, den ich geben werde, ist dies: Die Höhe des Baumes wird offensichtlich bestimmt, wenn man zu den "Blättern" kommt. Die Blätter eines Baumes, der die Wiederholungsrelation einer Funktion modelliert, sind der Basisfall. Daher würde ich darauf schauen, wie "schnell" N zum Basisfall schrumpfen kann.
Die Höhe des Rekursionsbaums hängt von dem fraglichen rekursiven Algorithmus ab. Nicht alle Divide and Conquer-Algorithmen haben einheitliche Höhenbäume, so wie nicht alle Baumstrukturen einheitliche Höhen haben. Wenn Sie die maximal mögliche Höhe des Algorithmus nicht bestimmen können, oder wenn Sie die tatsächliche Höhe des Baums zur Laufzeit berechnen müssen, können Sie eine globale Variable für die rekursive Funktion verwenden, sie beim Eingang der Funktion inkrementieren und dekrementieren es auf den Funktionsexit. Diese Variable zeigt die aktuelle Stufe der rekursiven Prozedur an. Bei Bedarf können Sie den Maximalwert dieser Variablen in einer zweiten Variablen pflegen.
Tags und Links computer-science recursion tree proof recurrence
