rekursions-Baum-Methode zu lösen, Wiederholungen

Übte ich die Rekursion tree Methode mit diesem link: http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html .. 1. Beispiel war in Ordnung, aber im zweiten Beispiel wird er berechnet die Höhe des Baumes als log(base 3/2) n .. Kann mir jemand sagen, wie er berechnet sich die Höhe ? Vielleicht eine dumme Frage, aber ich kann das nicht verstehen! 😐

InformationsquelleAutor Chandeep | 2012-09-12
  1. 8

    Lassen Sie mich versuchen es zu erklären. Der rekursions-Formel, die Sie haben T(n) = T(n/3) + T(2n/3) + n. Er sagt, Sie machen eine Rekursion Baum, der spaltet sich in zwei Teilbäume Größen n/3, 2n/3 und Kosten n auf dieser Ebene.

    Wenn Sie sehen, die Höhe wird bestimmt durch die Höhe des größten Teilbaum (+1). Hier den rechten Teilbaum, der mit 2n/3 element fahren die Höhe. OK?

    Wenn der oben genannte Satz ist klar, ermöglicht die Berechnung der Höhe. Auf der Höhe 1,wir haben n*(2/3) Elemente, auf der Höhe 2, wir haben n*(2/3)^2 Elemente,... wir halten Aufspaltung, bis wir ein element nach Links, also in Höhe h

     n*(2/3)^h <= 1
 (take log both side)
 log(n) + h*log(2/3) <= 0
 (log is an increasing function)
 h*log(3/2) >= log(n)
 h >= log(n)/log(3/2)
 h >= log3/2 (n)

    Ich würde vorschlagen, das Lesen der Master-Methode für die Rekursion aus Einführung in die Algorithmen - CLRS.

    • Gute Erklärung.
    InformationsquelleAutor Nishant
Schreibe einen Kommentar