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