フィボナッチ数列のアルゴリズム

フィボナッチ数列アルゴリズム

勉強がてらメモ

フィボナッチ数列とは

フィボナッチ数列」とは「前の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(n) = fib(n - 1) + fib(n - 2)

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(6) = fib(5) + fib(4)

であるが、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];
}