Ü3: Fibonacci-Beispiel (3)

[ln62cudi]

Hallo,

ich verstehe leider nicht ganz, wie man beim rekursiven Teil vom Baum aus zur Konklusion O(2^n) gelangt. Da steht: Weil die Anzahl der Kinder maximal 2^n steige, folgt O(2^n). Aber das Gleiche ist doch beim Rekursionsbaum bei zB MergeSort. Da wächst auch die Anzahl der Kinder mit maximal 2^n, so wie ich das sehe. Dennoch nimmt man da die Rekursionstiefe log(n).
Ich verstehe rein intuitiv, dass fibonacci in O(2^n) und mergesort in O(nlogn) ist, aber ich kann den Unterschied beim Rekursionsbaum nicht nachvollziehen. Ich denke, mir fehlt ein recht großer Gedankenschritt bei fibonacci.
Ich freu mich sehr, wenn mir jemand helfen kann.

Liebe Grüße,
Livia

[Carlito]

Hallo Livia,
so wie ich das verstanden habe reduziert sich bei deinem Sortier Beispiel ja die Problemgröße immer um die hälfte, bis nur noch ein Element vorhanden ist... deswegen log_2(n).
Beim Fibonacci Rekursionsbaum reduziert sich ja das Problem immer nur um 1 und um 2, solange bis n 1 oder 0 ist... somit erstellt jeden n>1 wieder 2 kinder und die Anzahl der Rekursionen wird größer und fächert sich wie in dem Bild in der Übung weiter auf... deswegen O(2^n)

[ln62cudi]

Okay, das hilft mir auf jedenfall schon mal etwas weiter. Aber wie genau kommt man auf die 2^n? weil bei mergesort ist es ja ganz einfach die rekursionsbaumtiefe und hier vielleicht weil jeder knoten zwei neue erzeugt. Aber vielleicht so gefragt: Wann weiß ich, dass ich die Rekursionbaumtiefe angucken muss und wann nicht?

[Carlito]

Die Tiefe des Rekursionsbaumes spielt immer eine Rolle bei der Komplexitätsuntersuchung von rekursiven Algorithmen die Antwort auf deine Frage wäre eher, was mit der Problemgröße passiert, die zu bearbeiten ist. Bei Mergesort halbiert sie sich jedes mal ungefähr und bei Fibonacci werden solange 1 oder 2 neue Aufrufe gestartet, bis die Problemgröße von n 0 oder 1 ist.