Ü3: Fibonacci-Beispiel (3)

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
ln62cudi
Neuling
Neuling
Beiträge: 9
Registriert: 13. Apr 2016 06:35

Ü3: Fibonacci-Beispiel (3)

Beitrag von ln62cudi » 5. Jun 2016 14:24

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
Erstie
Erstie
Beiträge: 12
Registriert: 5. Jun 2016 19:35

Re: Ü3: Fibonacci-Beispiel (3)

Beitrag von Carlito » 5. Jun 2016 19:47

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
Neuling
Neuling
Beiträge: 9
Registriert: 13. Apr 2016 06:35

Re: Ü3: Fibonacci-Beispiel (3)

Beitrag von ln62cudi » 5. Jun 2016 20:14

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
Erstie
Erstie
Beiträge: 12
Registriert: 5. Jun 2016 19:35

Re: Ü3: Fibonacci-Beispiel (3)

Beitrag von Carlito » 5. Jun 2016 23:52

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.

Antworten

Zurück zu „AuD: Theoretische Aufgaben“