Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Laufzeit Fibonacci-Zahlen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Laufzeit Fibonacci-Zahlen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

matze9999
Grünschnabel

Dabei seit: 06.05.2013
Beiträge: 5

Laufzeit Fibonacci-Zahlen

Zitatantwort auf diesen Beitrag erstellen

Hallo,
ich sollte die Laufzeit des auf dem Bild zu sehenden Alghoritmusses bestimmen. Bei dem Alghoritmus handelt es sich um die Berechnung der n-ten Fibonacci-Zahl.
Als weiteren Anhang habe ich die Lösung dieser Aufgabe mit hochgeladen.
Meine Frage nun, wie kommt man von
$[latex]n > 1: A(n) \leq 2A(n-1)+1[/latex]$ auf
$[latex]A(n) \leq 2^{n}-1 [/latex]$
bzw. von
$[latex]n > 1: A(n)\geq 2A(n-2)+1 [/latex]$ auf
$[latex]A(n) \geq 2^{\frac{n}{2} }-1 [/latex]$
Kommt man da durch Umformen auf das Ergebnis oder was wurde da angewandt.

Wäre super, wenn mir das mal jemand erklären könnte.

Vielen Dank

matze9999 hat diese Bilder (verkleinerte Versionen) angehängt:

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von matze9999: 23.05.2013 23:35.

23.05.2013 23:35

Nehmen Sie matze9999 in Ihre Freundesliste auf

Airblader Airblader ist männlich

Doppel-As

Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München

–

__________________
The best thing about a boolean is that even if you're wrong, you're only off by a bit.

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Airblader: 25.05.2013 16:04.

24.05.2013 08:13

Nehmen Sie Airblader in Ihre Freundesliste auf

Airblader Airblader ist männlich

Doppel-As

Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München

Edit: Sorry, aber ich kann es nicht leiden, wenn jemand eine Frage stellt und sich dann (mindestens) zwei Tage lang nicht meldet – das ist Zeitverschwendung. Wenn du eine Frage stellst und sich jemand die Zeit nimmt, zu antworten, dann nimm dir bitte auch die Zeit, dich mit der Antwort auseinanderzusetzen.

In diesem Sinne habe ich die (korrigierte) Lösung entfernt und verbleibe mit einem Tipp: Wiederholtes Anwenden der Abschätzung.

__________________
The best thing about a boolean is that even if you're wrong, you're only off by a bit.

Dieser Beitrag wurde 10 mal editiert, zum letzten Mal von Airblader: 25.05.2013 16:05.

24.05.2013 16:45

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo Airblader,

ich verstehe deinen Frust, aber ich finde es schade, wenn Du Antworten löschst. Schließlich können auch andere von deinen Antworten pofitieren, die danach im Forum suchen. So schreckst du vlt. potentielle Suchende und auch den Autor ab. Und ich schätze Deine Arbeit auf jeden Fall sehr.

VG,

Karlito

25.05.2013 17:56

Nehmen Sie Karlito in Ihre Freundesliste auf

Airblader Airblader ist männlich

Doppel-As

Dabei seit: 03.03.2013
Beiträge: 138
Herkunft: München

Ja, das ist mir bewusst – aber in erster Linie möchte ich den Fragesteller erziehen; andere, die über die Frage stolpern, spielen erstmal eine untergeordnete Rolle.
Und zu dieser Erziehung (für die ich nicht immer auf Gegenliebe stoße – aber so hat jeder seinen Stil) gehört eben auch, dass das Fragen-und-Antworten-"Spiel" gewisse Spielregeln hat, die selbstverständlich sein sollten. Ich investiere ja nicht nur einmal die Zeit, um zu antworten, sondern schaue danach ständig nach Rückmeldungen, d.h. ich bemühe mich darum, dass es zu keinen all zu langen Pausen kommt (gerade bei Hausaufgaben ist das sinnvoll, denn da gibt es ja eine Abgabefrist). Dies erwarte ich dann aber von meinem Gegenüber auch.

Das mag diesen Leuten dann vielleicht nicht schmecken, aber ich bin schließlich nicht dazu gezwungen, ihnen zu helfen. Gegebenenfalls tut es dann halt jemand anders.

__________________
The best thing about a boolean is that even if you're wrong, you're only off by a bit.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Airblader: 26.05.2013 00:20.

25.05.2013 20:57

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Laufzeit Fibonacci-Zahlen