Fibonacci Folge
-
@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?
