JavaScript アルゴリズム: フィボナッチ数列を解く (LeetCode)

フィボナッチ数は、一般にフィボナッチ数列F(n)と呼ばれる数列を形成し、各数は と から始まる先行する 2 つの数の合計になります。次の整数シーケンスの数字 0、1、1、2、3、5、8、13、21、34、55、89、……..01

あれは

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

例 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

この問題を解決するためのいくつかのオプションがあります:再帰アプローチ。

再帰アプローチ

数学的再帰関係を直接再帰的に実装した単純な方法。この問題を解決する最も遅い方法は、指数関数的な時間の複雑さ: O(2^N)と空間の複雑さ: O(N)がかかるためです。

メモ化による動的計画法（トップダウンアプローチ）

これまでに計算されたフィボナッチ数を保存することで、再帰的に行われる繰り返しの作業を避けることができます。すべての値をマップに格納するだけです。時間の複雑さ: O(N)および空間の複雑さ: O(N)。

反復アプローチ

すでに計算されたフィボナッチ値を使用して、すべてのサブ問題を解決し、N 個の要素の答えを返す反復。時間の複雑さ: O(N)および空間の複雑さ: O(N)。

反復アプローチ（スペース最適化）

前の 2 つの数値を格納する反復アプローチを最適化できるのは、次のフィボナッチ数を連続して取得するために必要なのはそれだけだからです。時間の複雑さ: O(N)および空間の複雑さ: O(1)。

行列累乗法

Matrix Exponentiation を使用して、結果の行列の(0, 0)の要素からフィボナッチ数を取得します。これを行うために、フィボナッチ数列の行列方程式に依存して、N 番目のフィボナッチ数を見つけることができます。

この式はどのように機能しますかWikiを見ることができます

このソリューションには、時間の複雑さ: O(logN)と空間の複雑さ: O(logN) があります。

数学のアプローチ

以下を使用できますgolden ratio forumula。

フィボナッチ数列と黄金比の仕組みについて詳しくは、こちらのリンクをご覧ください。

このソリューションには、時間の複雑さ: O(logN)と空間の複雑さ: O(1)があります。

また、特定の N の値を返すのではなく、特定の N までのフィボナッチ要素の配列を返す必要がある場合もあります。

例：

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

少し変更を加えたメモ化を使用した動的プログラミング:

フィボナッチ問題を解決するためのさまざまなオプションを検討しました。最も理解しにくいのは行列指数ですが、通常は、前の 4 つの方法の知識があれば面接に十分です。

お役に立てば幸いです。

読んでくれてありがとう！また近いうちにお会いしましょう。

その他のコンテンツはPlainEnglish.ioにあります。無料の週刊ニュースレターにサインアップしてください。Twitter、LinkedIn、YouTube、Discordでフォローしてください。グロースハッキングに興味がありますか？サーキットをチェックしてください。