Fibonacci-Interview

Die Berechnung der Fibonacci-Reihe ist eine klassische algorithmische Aufgabe, da sie häufig bei Interviews gegeben wird, wenn überprüft werden soll, ob der Kandidat im Prinzip zumindest irgendwie in Algorithmen fähig ist. Angenommen, Sie sind der gleiche Kandidat. Sie erhielten die Aufgabe: Schreiben Sie in JavaScript eine Funktion fib(n) , die die n-te Fibonacci-Zahl zurückgibt. Wir betrachten die Fibonacci-Zahl Null als Null. Eine Validierung des Arguments ist nicht erforderlich. Welche Möglichkeiten haben Sie?

1. Um einfacher zu sein und die Leute werden nach dir greifen.

Die einfachste Lösung ist ein banaler Zyklus.

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

Ein Witz. Natürlich müssen Sie nicht so schreiben - es sei denn, Sie werden nicht für die Position eines Vollzeit-Verschleierers interviewt.

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

Gehen Ihnen die variablen Gutscheine aus? Cypok

Okay, okay, für eine noch bessere Lesbarkeit schreiben wir Folgendes:

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

Dies ist eine klassische, einfache und elegante Option. Aber vielleicht möchten Sie Ihr Wissen über einige andere Konzepte demonstrieren? Zum Beispiel ...

2. Um die Rekursion zu verstehen, müssen Sie die Rekursion verstehen

Ja, Sie können beispielsweise demonstrieren, dass Sie eine Rekursion durchführen können. Zum Beispiel so:

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

Denken Sie an diese Option. Das ist es nicht wert. Es sollte nicht sein. Es ist unmöglich. Niemals. Dies ist schlimmer als das Treten von Welpen und vergleichbar mit einem kleinen Holocaust.

Sie fragen sich vielleicht warum. Führen Sie in diesem Fall einfach diesen Code aus und versuchen Sie beispielsweise, die Fifty Fibonacci-Zahl zu berechnen. Ich denke, Sie werden eine gewisse Verzögerung spüren. Ein Witz. Ich glaube, wenn Sie diesen Code nicht auf einem Supercomputer ausführen, werden Sie einfach nicht auf das Ergebnis warten. Trotz der Tatsache, dass der einfache, nicht rekursive Code aus den vorherigen Beispielen das fünfzigste Mitglied der Fibonacci-Sequenz schneller zählt, als Sie Zeit haben, das Wort „fünfzig“ oder eine Silbe zu sagen.

In der groben Sprache der O-Notation ausgedrückt, hat eine solche Lösung eine zeitliche Komplexität von O (e ⁿ ). Das heißt, die Ausführungszeit dieser Funktion wächst exponentiell mit zunehmendem n. Das heißt, wenn n um zunimmt, erhöht sich die Ausführungszeit um. Grob gesagt, wenn fib(45) eine Stunde warten musste, dann fib(46) , warten Sie zwei Stunden, fib(47) - 4 Stunden und so weiter. Ich kaue so detailliert, dass jeder Leser, selbst ein Schriftsetzer, der zuerst versucht hat, Skripte zu schreiben, den Schrecken der Situation erkennen konnte.

Das ist richtig, aber zu unhöflich. Sie können eine genauere Schätzung der Anzahl der Aufrufe der Funktion ~ (1 + sqrt (5)) fib (n) und der schönen Bemerkung erhalten: „Um die Fibonacci-Zahl mit einer naiven rekursiven Methode zu berechnen, benötigen Sie 3,2-mal mehr Funktionsaufrufe als die Fibonacci-Zahl selbst.“ Taus

Und wir bekommen eine andere Methode, um es zu berechnen. Sie müssen nur die naive rekursive Methode ausführen, die Anzahl der Funktionsaufrufe zählen und durch 3,2 dividieren! Cerberuser

Wenn Sie dieses Problem während eines Interviews rekursiv lösen müssen, ist dies höchstwahrscheinlich eine Falle. Eine „korrekte“ Rekursion, die in linearer Zeit arbeitet, könnte beispielsweise so aussehen:

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

Zusammenfassend: Trotz der Tatsache, dass Fibonacci-Zahlen ein klassisches Lehrbuchbeispiel für Rekursion sind, ist dies in Wirklichkeit nicht der bequemste Fall für die Anwendung von Rekursion. Sie können jedoch versuchen, mehr Wissen zu demonstrieren.

3. Gedenkveranstaltung

Es gibt einen magischen Weg, der eine ungeheuer unwirksame Lösung aus dem letzten Absatz in eine möglicherweise sehr schnelle Lösung verwandelt (wenn auch nicht ohne Probleme). Sein Name ist Memoization. Und wenn Sie Russisch sprechen, erinnern wir uns nur an die Ergebnisse früherer Anrufe, anstatt sie erneut zu berechnen.

Grundsätzlich können wir in dieser Lösung nicht einmal etwas ändern - fügen Sie einfach eine memoize Wrapper-Funktion hinzu. Hier verwende ich der Klarheit halber die vereinfachte Version für eine Funktion mit einem einzigen Argument.

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Voila! Jetzt hat die fib Funktion durch Schließen Zugriff auf das cache Objekt. Wenn es mit einem Argument aufgerufen wird, das zuvor nicht angetroffen wurde, wird der berechnete Wert im cache gespeichert. Bei neuen Funktionsaufrufen mit demselben Argument muss der Wert nicht neu berechnet werden, sondern wird einfach aus dem Cache entnommen. Das Hauptproblem der „schlechten“ alten fib Funktion bestand darin, dass die gleichen Werte mehrmals neu berechnet wurden. Um beispielsweise fib(45) zu berechnen, war es notwendig, f(44) einmal, zweimal f(43) , dreimal f(42) , fünfmal f(41) usw. zu berechnen.


Jetzt werden die vorherigen Werte einmal berechnet und wenn sie erneut angefordert werden - einfach aus dem Cache entnommen. Können Sie sich vorstellen, wie viel schneller wir jetzt die fünfundvierzigste Fibonacci-Zahl berechnen können? Ernsthaft, wann denkst du?

In der Tat - etwas langsamer. Ich habe absichtlich einen klassischen Fehler gemacht, der oft beim Auswendiglernen rekursiver Funktionen gemacht wurde. Wenn fib(45) "unter der Haube" genannt wird, wird oldFib(45) aufgerufen, das oldFib(44) und oldFib(43) für seine Bedürfnisse oldFib(43) ... oldFib(43) Sie den Haken? Im Folgenden wird bereits eine reguläre, nicht gespeicherte Funktion aufgerufen. Wenn wir fib(45) erneut aufrufen, erhalten wir natürlich sofort das Ergebnis aus dem Cache - der erste Aufruf wurde jedoch überhaupt nicht beschleunigt. Um dies zu beheben, müssen Sie noch oldFib unter den Schraubenschlüssel oldFib :

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Großartig! Jetzt funktioniert der erste Aufruf von fib(45) mit einer Geschwindigkeit, die mit der Version mit einer Schleife vergleichbar ist. Und weitere Herausforderungen werden in der Regel in konstanter Zeit funktionieren ... Ups! Wieder getäuscht. Das Abrufen des Werts der Eigenschaft eines Objekts per Schlüssel ist eine schnelle Operation, aber O (1) ist nur im Durchschnitt, im schlimmsten Fall kann es sich zu O (n) verschlechtern. Um es sehr gut zu machen, können wir in unserem Fall den cache Typ von einem Objekt in ein Array ändern.

Natürlich sollte man nicht vergessen, dass das Auswendiglernen Speicher benötigt. Und während wir die Zeitkomplexität reduzieren, wächst die Speicherkomplexität von O (1) auf O (n).

Wie können wir sonst angeben? Zum Beispiel, um Ihre tiefen Kenntnisse der Mathematik zu demonstrieren

4. Herr Binet

Es gibt eine spezielle, wunderbare Wissenschaft darüber, wie man Wiederholungsbeziehungen in explizite Formeln umwandelt. Hier werden wir nicht auf die Details eingehen. Wir werden nur sagen, dass wir für Fibonacci-Zahlen mit relativ einfachen Argumenten die folgende Formel ableiten können, die als Binet-Formel bekannt ist:

$$

$$F_n = \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n - \ left (\ frac {1 - \ sqrt5} {2} \ right) ^ n} {\ sqrt5}$$

Es ist jedoch eine ziemlich mathematische Sprache, wir schreiben sie in JavaScript:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

Fahren wir mit den ersten Zahlen weiter. Großartig, alles scheint zu funktionieren. Hier ist 13, hier ist 21, hier ist 34, hier ist ... 54.999999999999999999?

Ja, ein solches Ergebnis ist natürlich logisch. Die Binet-Formel ist mathematisch genau, aber der Computer arbeitet mit Bruchteilen endlicher Genauigkeit, und während der Operationen mit ihnen kann sich ein Fehler ansammeln, der in diesem Fall aufgetreten ist. Wir können es jedoch beheben. Da wir wissen, dass der im Zähler subtrahierte Wert immer klein ist, können wir die Formel auf den folgenden Zustand vereinfachen:

$$

$$F_n = \ left \ lfloor \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n} {\ sqrt5} \ right \ rceil$$

Hier bedeuten seltsame unvollendete eckige Klammern die nächste ganze Zahl, dh die Rundung. Schreiben Sie unseren Code neu:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

Ja, das ist viel besser. Wir können sowohl 55 als auch 89 sehen, und sogar meine Lieblings-Fibonacci-Zahl ist 144 (was ich liebe, weil sie zwölf Quadraten entspricht). Bis zur Zahl 76 wird alles in Ordnung sein. Diese sollte gleich 3416454622906707 sein, und unsere Funktion berechnet 3416454622906706. Da das Problem der begrenzten Genauigkeit von Bruchzahlen nicht verschwunden ist, haben wir es nur tiefer geschoben und gehofft, dass es nicht auftaucht. Wie dieses Beispiel zeigt, hofften sie vergebens.

Tatsächlich können wir etwas anderes tun, um diese Methode zu speichern. Aber mehr dazu weiter unten. In der Zwischenzeit - Witze beiseite. Lassen Sie uns über die harte, hardcore und brutale Methode sprechen.

5. Folgen Sie dem weißen Kaninchen.

Sie sagen, wenn Sie ein Problem haben und Ihnen die Idee gekommen ist, es mit regulären Ausdrücken zu lösen, haben Sie jetzt zwei Probleme. Matrizen sind im Gegenteil reguläre Ausdrücke. Viele Probleme werden, wenn sie in der Sprache der Matrizen umformuliert werden, einfach von selbst gelöst.

Was die Fibonacci-Zahlen betrifft, so können Sie für sie in Matrixsprache diese offensichtliche Identität schreiben:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} \ begin {pmatrix} F_ {n - 1} \\ F_n \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n +1} \ end {pmatrix}$$

Das heißt, wenn wir ein Paar aufeinanderfolgender Fibonacci-Zahlen nehmen und sie mit einer so einfachen Matrix multiplizieren, erhalten wir das folgende Paar. Daraus folgt die logische Schlussfolgerung: Wenn wir ein Paar von Null- und ersten Fibonacci-Zahlen, dh Null und Eins, nehmen und sie mit dieser Matrix mit einer n-ten Potenz multiplizieren, erhalten wir ein Paar von n-ten und en plus dem ersten Fibonacci. Das heißt, menschlich gesprochen:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n \ begin {pmatrix} 0 \\ 1 \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n + 1} \ end {pmatrix}$$

Sie können dies etwas vereinfachen, indem Sie Vektoren aufgeben. Tatsächlich sind alle erforderlichen Werte in der Matrix selbst enthalten:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_ {n} \\ F_ {n} & F_ {n + 1 } \ end {pmatrix}$$

Großartig, nicht wahr? Es bleibt zu verstehen, was für eine Arschharmonie, wenn er kein Philharmoniker ist. Ich meine - warum sind solche Schwierigkeiten aus heiterem Himmel? Und die Antwort ist einfach - schnelle Potenzierung.

Wie viele Elementarmultiplikationen sind erforderlich, um beispielsweise 2 ¹⁰ zu berechnen? Ein normaler Mensch wird neun sagen. Zweimal zwei - vier. Zweimal vier - acht. Zweimal acht ist sechzehn. Usw. Eine listige Person wird das vier sagen.

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

Der Programmierer wird sagen. dass er sich auswendig an diese Zahl erinnert und nichts multipliziert werden muss. Wir haben jedoch oben die Probleme der Memoisierung erörtert.

Eine schnelle Exponentiation ist also auch auf Matrizen anwendbar und ermöglicht es uns, die asymptotische Zeitkomplexität unserer Funktion von O (n) auf O (log n) zu reduzieren. Und das ist sehr cool - es sei denn natürlich, diese Komplexität ist uns wirklich so wichtig. Schreiben wir den Code:

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

Wir haben also den schnellsten Algorithmus im Wilden Westen. Und es kann, anders als die meisten vorherigen, bei einem Interview nicht ironisch demonstriert werden. Und an einigen mathematisch-leistungsfähigen Orten wird es von Ihnen erwartet.

PS

Ich habe eine Bemerkung versprochen, wie eine Methode basierend auf der Binet-Formel gespeichert werden kann. Die Antwort liegt in meinem Artikel. Dort schrieb ich für die Bedürfnisse der Volkswirtschaft eine spezielle Klasse, die Wurzel von fünf rationalen Zahlen, die ohne Genauigkeitsverlust die Ergebnisse von arithmetischen Operationen auf ganzen Zahlen und eine Wurzel von fünf speichern kann. Sie können diese Klasse nehmen, sie mit der Rundungsmethode ergänzen und damit nach Fibonacci-Zahlen mit der Binet-Formel suchen. Und dann Lachgas durch schnelle Exponentiation injizieren.

Und was am interessantesten ist: Wenn Sie sich genau ansehen, welche Zahlen im Prozess erhalten werden, welche Operationen ausgeführt werden, wird klar, dass diese Methode dieselbe Matrixmultiplikation ist, nur unter einer anderen Fassade. Der einzige Unterschied besteht darin, ob wir Zahlen in zweidimensionalen Arrays oder in den Feldern eines Objekts einer speziellen Klasse speichern.

Das ist alles Wenn Sie der Meinung sind, dass ich einige andere interessante Möglichkeiten verpasst habe, um Zahlen zu finden, die niemand braucht, schreiben Sie dies unbedingt in den Kommentaren.

Es gibt auch eine Methode wie das schnelle Verdoppeln . Es funktioniert wie eine Matrixmultiplikation in O (log), jedoch mit einer kleineren Konstante in der Asymptotik (und in der Praxis). Kurz gesagt, dann werden dort zwei Formeln verwendet, auf deren Grundlage man schnell rekursiv auf zweimal niedrigere Indizes zurücksetzen kann:

F _2n = F _n * (2 * F _{n + 1} - F _n )
F _{2n + 1} = F _n ² + F _{n + 1} ²

Die Implementierung ist übrigens recht kompakt.

Vergleich der Geschwindigkeit verschiedener Methoden

just_maksim