フィボナッチ数
定義
$ F_0 = 0
$ F_1 = 1
$ F_n = F_{n-2} + F_{n-1} \ (n \geq 2)
数列
0から20まで
code:js
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 一般項
黄金数$ \varphi = \frac{1 + \sqrt{5}}{2} = 1.618033988\cdots のとき、 $ F_n = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt{5}}
Desmos
https://gyazo.com/b1b664e25f8b585cecc09146602dc89d
コード
ナイーブな実装
n < 0 のバリデーションとかしてない、すごいシンプルな実装
計算量$ O(\varphi^n)
code:js
function fib( n ) {
if ( n < 2 ) { return n; }
return fib( n - 2 ) + fib( n - 1 );
}
メモ化再帰
計算量$ O(n)
code:js
function fib( n ) {
if ( result == null ) {
result = memo n = fib( n - 2 ) + fib( n - 1 ); }
return result;
}
行列
$ (F_n, F_{n+1})をベクトルに見立てると、
$ f: \mathbb R^2 → \mathbb R^2、$ (F_n, F_{n+1}) → (F_{n+1}, F_{n+2})という写像が作れる
$ \begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix}
さらに、
$ \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}
$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^nの計算を$ A^{2n} = (A^2)^nを使って最適化すると、
これは$ O(\log_2 n)になります すご
code:js
import { mat2Multiply } from '@0b5vr/experimental';
function fibMatrix( n ) {
if ( n === 1 ) {
} else if ( n % 2 === 0 ) {
const m = fibMatrix( n / 2 );
return mat2Multiply( m, m );
} else {
return mat2Multiply( 1, 1, 1, 0 , fibMatrix( n - 1 ) ); }
}
function fib( n ) {
if ( n < 2 ) { return n; }
return fibMatrix( n ) 0 ; }
ちなみに一般項の導出もこの行列をいじってやっていくそうですよ
線形代数の知識が必要そうで、ぼくにはちょっと難しい 長方形