Wie wird man die Höhe eines Rekursionsbaums ermitteln, der bei wiederkehrenden Laufzeiten erstellt wird? Wie unterscheidet es sich von der Höhe eines normalen Baumes?Wie kann die Höhe eines Rekursionsbaums aus einer Rekursionsbeziehung ermittelt werden?
alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif
edit: sorry, meinte ich hinzufügen, wie die Höhe des Rekursionsbaumaus der Rekursion zu erhalten.
Die Höhe des Rekursionsbaums hängt vom 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.
Erstens, wenn dies eine Hausaufgabenfrage ist, 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 Haupthinweis, den ich geben werde, ist dies: Die Höhe des Baumes wird offensichtlich bestimmt, wenn Sie zu den "Blättern" kommen. 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.
Dies ist keine Hausaufgaben:) Persönliches Studium. Das Bild, das ich verlinkt habe, war am relevantesten für Google-Bilder. Sollte das vorher geklärt haben, sorry! – Chris
Entschuldigung, der Kommentar wurde zu früh hinzugefügt. Deine Antwort macht definitiv Sinn. Es ist jedoch normalerweise nicht der Fall, dass Sie den Blättern ganz nach unten folgen können. Das Erstellen der ersten Zweige ist trivial. Von da an hat mich das ein bisschen verwirrt :) – Chris
Wenn die Wiederholung in Form von T (n) = aT (n/b) + f (n) ist, dann ist die Tiefe des Baums logarithmische Basis b von n.
Zum Beispiel hätte 2T (n/2) + n Wiederholung Baum der Tiefe Ig (n) (Log-Basis 2 von n).
Schießen von meinem Hintern hier, aber ich sehe keinen Unterschied. Warum denkst du, dass es einen Unterschied gibt? In der Zusammenfassung sind sie beide Bäume ... –
sehen meine Antwort hier: http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly/13093274#13093274 – 2cupsOfTech