フィボナッチ数列のアルゴリズム
フィボナッチ数列のアルゴリズム
勉強がてらメモ
フィボナッチ数列とは
「フィボナッチ数列」とは「前の2つの数を加えると次の数になる」という数列。1番目は0、2番目は1。n番目の数字は(n - 1)番目と(n - 2)番目の数字の和。
例えば、6番目の数は5 (0, 1, 1, 2, 3, 5)
アルゴリズム実装(1) O(n2)
n番目のフィボナッチ数をfib(n)
とすれば、
fib(4)
を求めるには
1 fib(4) ________________|________________ | | 2 fib(3) fib(2) ________|________ ________|________ | | | | 4 fib(2) fib(1) fib(1) fib(0) ________|________ | | 0 fib(1) fib(0)
となるので、計算量はO(n^2)
1番目と2番めの例外に注意してこれを実装すると次のようになる:
function getFib(n) { if (n === 2) { return 1 } else if (n === 1) { return 0 } return getFib(n - 1) + getFib(n - 2) }
アルゴリズム実装(2) O(n)
先程の樹形図を見ると、fib(2)
などすでに答えがでているものでも計算しているので、改善の余地があることに気づく。
一度出した答えを覚えておいて再利用できるならば、fib(4)
の答えを得た時、例えばfib(6)
を新たに求めたい場合は
であるが、fib(4)
の答えはわかっているので、fib(5)
だけを求めれば良い。同様にfib(n)
を求めたい時、fib(n - 1)
だけを求めれば良いから計算量はO(n)
これを実装するとき、fibStore
配列にフィボナッチ数列を格納する。インデックスi
の数字はfibStore[i - 1] + fibStore[i - 2]
である。したがって
function getFib(n) { if (n === 2) { return 1 } else if (n === 1) { return 0 } const fibStore = [0, 1]; for (let i = 2; i < n; i ++) { const ithFib = fibStore[i - 1] + fibStore[i - 2] fibStore[i] = ithFib } // n番目のフィボナッチ数 (インデックス n - 1) return fibStore[n - 1]; }