[データ構造/アルゴリズム]211011フィボナッチ数列を用いて#関数を効率的に解く


📌 フィボナッチ数列(効率的な解)


私たちがよく知っているフィボナッチ数列は再帰的に解くことができる.しかし、トイ問題で望ましいのは効果的な解決だ.
function fibonacci(n) {
 if( n === 0 ) {
  return 0;
} else if( n===1 ) {
  retrun 1; 
} 
 return fibonacci(n-2) + fibonacci(n-1)
この形態は最も基本的な形態であるべきで,有効な解決方法がある.上のコードのみで解読すると、テストボックスには実行時間を超える文字が表示されます(効率が低下しているようです)
だから違う方法で近づかなければなりません.私の永遠の射手googleを通じて、私は異なるコードで近づくことができます.
最初の近似:0と1は固定されています.
フィボナッチ数列を書いてください.
0,1,1,2,3,5,8,13 ....
上に書いたコードのように、どんなパラメータ(=n)を入れても、固定された数字は0と1です.
変数newArrで[0,1]を設定します.
2つ目の方法:0と1の後の数値を処理する関数を作成します.
nは前に作成したnewArrを使用する新しい関数を作成します.newArrの0番目のインデックスは0に固定され,1番目のインデックスは1に固定される.これらはnewArr[0]=0とnewArr[1]=1で現れるため、未定義は現れない.ただし、newArr[2]は現在値がないためundefinedが現れる.
let newFinbonacci = (n) => {
  if( newArr[n] !== undefined) {
     return newArr[n] // n이 0이거나 1일 때는 [0,1]을 리턴한다
  } 
  // 그렇지 않을 때
}
newArr[n]の値が定義されていない場合は、再帰関数(newArr[n]に値がない)を使用します.
これでnewArr[n]の値にUndefinedが表示されると、再帰関数を使用して返されます.
newArr[n] = newFibonnaci(n-2) + newFibonnaci(n-1)
次に、この関数の外のscopeで新しく作成した関数を返します.

検査する事項


ここで注意しなければならないのは,関数が呼び出された瞬間,順序に従って行われないことである.下記を確認します.

関数を見つけた瞬間、一番下のnewFibonacciを実行し、関数を返します.そして再帰を繰り返す.nは0より大きい整数に設定されているため、nが0の場合、0を返して最終的に終了する.
リファレンス

  • フィボナッチ数列を効果的に実現する方法
    https://velog.io/@devjade/フィボナッチ-数列-効率-ダイナミック-プログラミング

  • ゼロに戻るブログ
    https://www.zerocho.com/category/JavaScript/post/579248728241b6f43951af19