pythonフィボナッチ数列アルゴリズム

フィボナッチ数は、通常F(n)で表され、形成されたシーケンスをフィボナッチ数列と呼ぶ.この数列は0と1から始まり、後ろの各数字は前の2つの数字の和です.つまり、
F(0)=0,F(1)=1 F(n)=F(n−1)+F(n−2)であり,n>1がnを与えるので,F(n)を計算してください.
例1:
入力:2出力:1
解釈:F(2)=F(1)+F(0)=1+0=1
じゅんかいき
再帰には、ベース・インスタンスと再帰関係式の2つの基本要素があります.

基本例:F(0)=0,F(1)=1,すなわち再帰終了箇所

再帰関係式:F(n)=F(n-1)+F(n-2)

def fib(n):
   #base case
   if n <= 1:
      return n
   elif n >= 2:
      return fib(n-1) + fib(n-2)

pythonの構文特性に基づいて、一言に略すことができます.

def fib(n):
  return fib(n-1) + fib(n-2) if n >= 1 else n

F(20) = F(19)+F(18)
F(19) = F(18)+F(17)
次に,F(18)反復,すなわち冗長構造を見出した.このような演算時間は大きくなり、
ノード数*サブ問題ごとに要する時間=時間の複雑さ
この場合O(2^N)であることが明らかになった.
純粋な再帰的な欠点は,過剰な冗長構造の存在にある.
再帰的に記憶を加え、指数級時間を多項式級時間にする.
私たちはすでに計算されたメモの中に存在することができます.そうすれば、次の計算の前に、まず表を調べておけばいいので、再計算する必要はありません.

memo = {
     }
def fib(n):
    #  
    if n in memo:
       return memo[n]
    #base case:
    elif n <= 1:
       return n
    else:
       ans = fib(n-1) + fib(n-2)
       memo[n] = ans
       return memo[n]

もちろん,上記のメモは配列を用いることもできるし,ハッシュテーブルを用いることもできる.
また,完璧さを追求すれば,ベース例をメモに格納することができ,ある程度の空間的複雑さを減らすことができる.
memo = {0:0,1:1}
ここでは上から下へのアプローチを紹介しますが、もちろん下から上へのアプローチも可能です.純再帰よりはよいが,時間的複雑度は依然として高く,leetcodeでは1500−1600 ms程度であった.
bottem-up-solution

def fib(n):
    memo = {
     0:0,1:1}
    for i in range(2,n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

forループの左側はメモにキー0,1が入っているので2から.そして最後に計算するのはmemo[n],i=nなのでn+1
この時間の複雑さは大幅に低下し,両者はルックアップテーブルのように見えるが,下から上へのこのような関数は再反復せず,テーブルを絶えず計算するだけである.leetcodeデータは36 ms
アルゴリズムの最適化はここまでですが、空間の複雑さについてはもっと最適化することができます.

import sys

h = {
     0:0,1:1}
l = [0,1]

print(sys.getsizeof(h))
print(sys.getsizeof(l))

#232
#72

辞書の空間的複雑さはリストよりはるかに大きいので、より最適化できます.一方,複雑さは要素サイズとは無関係である.要素の個数に関係します.

def fib(n):
    if n == 0:
       return 0
    memo[1 for i in range(n+1)]
    memo[0],memo[1] = 0,1

    for i in range(2,n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

最初のローがlen=n+1を生成する理由については、最後にインデックスがnであるため、インデックスは0から始まる
また、リストジェネレータの表現に加えてmemo=[1]*(n+1)
生成長n+1のリストを抽出するのは,リストインデックスが不十分であることを防止し,秩序ある置換を行うためである.
置換されているため、初期化リストの値は任意であり、ベース例が正しいことを保証すればよい.
0の先頭にないif文を入力するとエラーが発生するので注意してください(forループ)
また、力ボタンの多くの場合、判別が間違っているので、みんなは死の中で最適化して、いくつかの最適解を見ていればいいです.100%を求める必要はありません.みんなはいくつかの100%をコピーすることができます.いくつかは運100%で、あなたまで100%ではありません.
最後に,拡張として変数をスクロールする方法もある.

def fib(n):
    if n == 0:
       return 0
    for i in range(n):
        a,b = b,a+b
    return a

この方法は明らかに最適解ではないが,いくつかの本のpythonのコード仕様に従うと言う価値がある.この構造は可読性が悪いので、あまり使わないことをお勧めします.皆さんがよかったら、githubに行って小さな星をくださいね.https://github.com/sherlcok314159/leetcode-python-3/blob/main/fibo.md