与えられたシリーズ
Fib（1）* Fib（n + 2）+ Fib（2）* Fib（n + 1）+ Fib（3）* Fib（n）+ ...... + Fib（n-1）* Fib（ 4）
または合計 Fib（x）* Fib（n-x + 3）ここで、xは1からn-1まで変化します。ここで、Fib（n）はフィボナッチ数列のn番目の数です。
この級数を評価するために、Fib（n）は行列指数を使用して計算できます。
ただし、これの複雑さはlognであり、n個の用語の場合はnlognになります。
このシリーズを単一の用語またはその他の最適化に減らして、時間の複雑さを改善したいと思います。*
助言がありますか ？？
合計を 1 つの項に減らすことはできませんが、5 つの項の合計に減らすことはできます。これにより、O(log n)算術演算の複雑さが軽減されます。
ただし、ビットFib(n)がΘ(n)あるため、ビット操作の数は対数ではありません。Fib(n)とのサイズの数値の乗算があるn-1ため、ビット操作の数は ですM(n,log n)。ここで、 はビット数とビット数M(a,b)の乗算のビット操作の複雑さです。単純なアルゴリズムの場合、、したがって、以下のアルゴリズムのビット操作の数は です。abM(a,b) = a*bO(n*log n)
この削減を可能にする事実は、フィボナッチ数 (線形再帰によって定義される数列内のすべての数と同様) が純粋な指数項の和として記述できることです。特に、
Fib(n) = (α^n - β^n) / (α - β)
どこ
α = (1 + √5)/2; β = (1 - √5)/2.
フィボナッチ数に加えて、フィボナッチ数と同じ繰り返しに従うルーカス数も使用します。
Luc(n) = α^n + β^n
したがって、ルーカス数のシーケンス (インデックス 0 から始まる) は次のように始まります。
2 1 3 4 7 11 18 29 47 ...
この関係Luc(n) = Fib(n+1) + Fib(n-1)により、フィボナッチ数とルーカス数の間の簡単な変換が可能になりLuc(n)、O(log n)段階的な計算でフィボナッチ コードを再利用できます。
したがって、上記のフィボナッチ数の表現で、
(α - β)^2 * Fib(k) * Fib(n+3-k) = (α^k - β^k) * (α^(n+3-k) - β^(n+3-k))
= α^(n+3) + β^(n+3) - (α^k * β^(n+3-k)) - (α^(n+3-k) * β^k)
= Luc(n+3) - ((-1)^k * α^(2k) * β^(n+3)) - ((-1)^k * α^(n+3) * β^(2k))
関係を使用しα * β = -1ます。
さて、α - β = √5合計k = 1, ..., n-1が得られるので
n-1 n-1 n-1
5 * ∑ Fib(k)*Fib(n+3-k) = (n-1)*Luc(n+3) - β^(n+3) * ∑ (-α²)^k - α^(n+3) * ∑ (-β²)^k
k=1 k=1 k=1
幾何学的和は閉じた形式で書くことができ、少しジャグリングすると式が得られます
n-1
∑ Fib(k)*Fib(n+3-k) = [5*(n-1)*Luc(n+3) + Luc(n+2) + 2*Luc(n+1) - 2*Luc(n-3) + Luc(n-4)]/25
k=1
手順:
std::vector<int>必要なすべてのフィボナッチ数を定義して入力します。動的計画法を使用してこれらの数値を計算します。つまり、すでに計算した結果を利用します。同じ値を複数回計算しないでください!
ベクトルに必要なすべての数値を入力したら、式Fib(x) * Fib (n-x+3)をループで適用し、積の合計を計算します。
とを仮定f(n)=f(n-1)+f(n-2)するn>2とf(1)=f(2)=1、f(0)=0
させE(n)=sum(k=1 .. n-1, f(k)f(n-k+3))て、E'(n)=sum(k=0 .. n, f(k)f(n-k))
明らかにE(n)=E'(n+3) - ( f(0)f(n+3) + f(n)f(3) + f(n+1)f(2) + f(n+2)f(1) + f(n+3)f(0) )
wolframではE'(n)= (nL(n)-f(n))/5、: が見つかります。L(n)=f(n+1)+f(n-1)
これから ：
5E(n)=(n+3)( f(n+4)+f(n+2) ) - 5(2f(n) + f(n+1) +f(n+2))
5E(n)=(n+3)( 4f(n+1)+3f(n) ) - 10f(n+1) -15f(n)
5E(n)= (4n+2)f(n+1) + (3n-6)f(n)
評価が簡単であること、複雑さは使用されるフィボナッチ アルゴリズムと同じであること、
ルーカス数がわかれば、ID を使用できます...
F(n)*F(m) = [L(m+n) - (-1)^n*L(mn)]/5
これは、フィボナッチ数の積の合計をルーカス数の合計に減らします。
さらに良いことに、n+m は各項で一定であるため、合計はさらに減少します。この合計には n-1 項があるため、合計はルーカス数の合計になります。
[(n-1)*L(n+3) + L(n+1) - L(n-1) + L(n-3) - ... + (-1)^(n-1)* L(5-n)]/5
テストとして、n = 5 の場合、40 が得られます。これは積の直和と一致しています。
1*13 + 1*8 + 2*5 + 3*3 = 40
n = 1000 の場合、次の合計が得られます。
82283375600539014079871356568026158421560221654785733943009487102720 211767741849325389562067921531531130739623611293922046989610820831567088 516047002196966545744637588824274730947688693969572937880383134671205375
さらに良いことに、負のインデックスのルーカス数は正のインデックスのルーカス数と単純な関係にあるため、いくつかの追加作業により、ルーカス数の合計がさらに縮小されます。
k 番目のルーカス (および k 番目のフィボナッチ) 数を計算する限り、ここに示すように非常に効率的に実行できます。