Fibonacci Folge
-
Das Problem ist quadratischer Aufwand, da bei einem naiven Algorithmus der Speicher für das Zwischenergebnis schnell anwächst.
-
@deadc0de sagte in Fibonacci Folge:
@TGGC ich verstehe das Problem nicht...
Das könnte etwas länger dauern, wenn man nicht klug berechnet. Berechne es folgendermaßen:
und schau, was oben links rauskommt...
Ob der Aufwand wirklich quadratisch ist? Also die Potenz ist logarithmischer Aufwand (die Zahlen werden aber immer größer, mit denen man rechnet). Ich bezweifle mal, dass es gesamt quadratisch ist.
-
@wob sagte in Fibonacci Folge:
Ob der Aufwand wirklich quadratisch ist? Also die Potenz ist logarithmischer Aufwand (die Zahlen werden aber immer größer, mit denen man rechnet). Ich bezweifle mal, dass es gesamt quadratisch ist.
Die Addition wird linear teurer mit der Länge der beteiligten Zahlen. Da wir O(N) Additionen machen, deren Länge auch mit O(N) skaliert, kommt insgesamt O(N²) heraus.
-
@SeppJ das stimmt, allerdings ist das bei der Fibonacci Folge kaum zu vermeiden. Mit diesem Algorithmus braucht man etwa 10 Sekunden für die 1.000.000te Folge und das ist schon ziemlich gut denke ich, weil das Ergebnis auf die Ziffer genau ist.
-
-
@wob sagte in Fibonacci Folge:
@SeppJ sagte in Fibonacci Folge:
Da wir O(N) Additionen machen
Sind das nicht eher O(log n)?
Wie? Die Schleife geht von 0 bis N-2. Eine besseres Beispiel für O(N) gibt es wohl kaum.
Es ginge natürlich prinzipiell insgesamt in O(log(N)), aber das soll der Threadersteller mal schön selber rausfinden, wie.
-
@SeppJ meinst du die "closed form"? Weil wenn nicht... dann steig ich grad aus
-
@hustbaer sagte in Fibonacci Folge:
@SeppJ meinst du die "closed form"? Weil wenn nicht... dann steig ich grad aus
Ja. Ich gehe davon aus, dass wollen auch TGGC und wob sehen.
-
@SeppJ sagte in Fibonacci Folge:
Wie? Die Schleife geht von 0 bis N-2. Eine besseres Beispiel für O(N) gibt es wohl kaum.
Wozu habe ich ein Video verlinkt und die Formel daraus nochmal aufgeschrieben? Bestimmt nicht, um eine schlechtere Variante zu diskutieren.
Man kann auch fib(n) berechnen mit Hilfe von . https://en.wikipedia.org/wiki/Square_root_of_5#Relation_to_the_golden_ratio_and_Fibonacci_numbers
Aber auch da müsste man mal schauen, wie die Komplexität so aussieht, weil man ja eine gewisse Anzahl von Nachkommastellen braucht...
-
@wob Gibts da neben Binet's Formel nicht noch eine andere Möglichkeit?
-
@wob sagte in Fibonacci Folge:
@SeppJ sagte in Fibonacci Folge:
Wie? Die Schleife geht von 0 bis N-2. Eine besseres Beispiel für O(N) gibt es wohl kaum.
Wozu habe ich ein Video verlinkt und die Formel daraus nochmal aufgeschrieben?
??? TGGC und ich haben dem Threadersteller erklärt, warum seine jetzige Variante nicht so gut ist. Eben weil sie O(N²) ist.
@Swordfish sagte in Fibonacci Folge:
@wob Gibts da neben Binet's Formel nicht noch eine andere Möglichkeit?
Siehe wobs Beitrag mit der Matrix.
-
-
@Swordfish ist auf jeden Fall ein relativ spannendes Projekt. Ich sitze da auch schon seit Tagen dran das ganze zu optimieren.
-
Ähh, du weißt schon, dass es Lexika gibt, in denen steht, wie die grundlegenden Ideen zur effizienten Berechnung aussehen?
