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)
pythonの構文特性に基づいて、一言に略すことができます.
F(20) = F(19)+F(18)
F(19) = F(18)+F(17)
次に,F(18)反復,すなわち冗長構造を見出した.このような演算時間は大きくなり、
ノード数*サブ問題ごとに要する時間=時間の複雑さ
この場合O(2^N)であることが明らかになった.
純粋な再帰的な欠点は,過剰な冗長構造の存在にある.
再帰的に記憶を加え、指数級時間を多項式級時間にする.
私たちはすでに計算されたメモの中に存在することができます.そうすれば、次の計算の前に、まず表を調べておけばいいので、再計算する必要はありません.
もちろん,上記のメモは配列を用いることもできるし,ハッシュテーブルを用いることもできる.
また,完璧さを追求すれば,ベース例をメモに格納することができ,ある程度の空間的複雑さを減らすことができる.
memo = {0:0,1:1}
ここでは上から下へのアプローチを紹介しますが、もちろん下から上へのアプローチも可能です.純再帰よりはよいが,時間的複雑度は依然として高く,leetcodeでは1500−1600 ms程度であった.
bottem-up-solution
forループの左側はメモにキー0,1が入っているので2から.そして最後に計算するのはmemo[n],i=nなのでn+1
この時間の複雑さは大幅に低下し,両者はルックアップテーブルのように見えるが,下から上へのこのような関数は再反復せず,テーブルを絶えず計算するだけである.leetcodeデータは36 ms
アルゴリズムの最適化はここまでですが、空間の複雑さについてはもっと最適化することができます.
辞書の空間的複雑さはリストよりはるかに大きいので、より最適化できます.一方,複雑さは要素サイズとは無関係である.要素の個数に関係します.
最初のローがlen=n+1を生成する理由については、最後にインデックスがnであるため、インデックスは0から始まる
また、リストジェネレータの表現に加えてmemo=[1]*(n+1)
生成長n+1のリストを抽出するのは,リストインデックスが不十分であることを防止し,秩序ある置換を行うためである.
置換されているため、初期化リストの値は任意であり、ベース例が正しいことを保証すればよい.
0の先頭にないif文を入力するとエラーが発生するので注意してください(forループ)
また、力ボタンの多くの場合、判別が間違っているので、みんなは死の中で最適化して、いくつかの最適解を見ていればいいです.100%を求める必要はありません.みんなはいくつかの100%をコピーすることができます.いくつかは運100%で、あなたまで100%ではありません.
最後に,拡張として変数をスクロールする方法もある.
この方法は明らかに最適解ではないが,いくつかの本のpythonのコード仕様に従うと言う価値がある.この構造は可読性が悪いので、あまり使わないことをお勧めします.皆さんがよかったら、githubに行って小さな星をくださいね.https://github.com/sherlcok314159/leetcode-python-3/blob/main/fibo.md
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つの基本要素があります.
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