Rekursion Baum, Die Lösung Wiederholung Gleichungen

Question

Soweit ich weiß gibt Es 4 Wege zur Lösung Wiederholung Gleichungen :1 - Rekursion Bäume 2 - Substitution 3 - Iteration 4 - Derivat

Wir sind aufgefordert, Substitution, die wir benötigen, zu erraten, eine Formel für die Ausgabe.Ich lese aus CLRS Buch, dass es ist keine Magie, um dies zu tun, ich war neugierig, ob es irgendwelche Heuristiken, um dies zu tun?

Ich kann sicherlich eine Idee haben, indem er eine Wiederholung Baum oder mittels iteration aber, weil der Ausgang wird in Big-OH-oder Theta-format, Formeln nicht unbedingt übereinstimmen.

Hat jemand eine Empfehlung für die Lösung Wiederholung Gleichungen mit substitution?

Answer 1

Für die einfach sind, nehmen Sie nur "angemessen" zu erraten.

Für mehr kompliziert, würde ich gehen Sie vor und verwenden Sie ein Rezidiv Baum — es scheint mir der einfachste "Algorithmus" für die Erstellung einer Vermutung.Beachten Sie, dass es schwierig sein kann zu verwenden, einem Rezidiv Baum zu beweisen, dass eine gebundene (die details sind schwer zu bekommen Recht).Wiederholung Bäume sind sehr nützlich für die Bildung von Vermutungen, die dann bewiesen durch substitution.

Ich bin mir nicht sicher, warum sagst du, dass die Formeln nicht übereinstimmt mit der Ausgabe in der Big-O-oder Theta.Sie in der Regel nicht exakt übereinstimmen, aber das ist Teil des point-of-Big-O.Teil der trick geht zurück auf eine substitution ist, zu wissen, wie Sie Stecker in die Big-O die Lösung für die substitution in der algebra zu arbeiten.IIRC, CLRS funktioniert ein Beispiel oder zwei von diesem.

Answer 2

Bitte beachten Sie, dass die Liste der möglichen Wege zur Lösung Wiederholung Gleichungen ist definitiv nicht komplett sein, lediglich eine Reihe von tools, die Sie unterrichten, Informatiker, weil Sie höchstwahrscheinlich lösen die meisten Ihrer Probleme.

Für exakte Lösungen der Wiederholung Gleichungen, Mathematiker verwenden Sie ein tool namens erzeugende Funktionen.Erzeugende Funktionen geben Ihnen exakte Lösungen, und im Allgemeinen sind leistungsfähiger als das master-theorem.

Es ist eine großartige Ressource, online lernen, über das hier. http://www.math.upenn.edu/~wilf/DownldGF.html

Wenn Sie gehen durch die ersten paar Beispiele sollten Sie erhalten die hängen von es in keine Zeit.

Sie müssen einige mathematische hintergrund und zu verstehen, rudimentäre taylor-Reihe. http://en.wikipedia.org/wiki/Taylor_series

Erzeugende Funktionen sind auch sehr nützlich in Wahrscheinlichkeit.