Rでフィボナッチ数！(動的計画法版)

計算量爆発しろ(違

先ほどのfib(n)は、nの値が大きくなると計算量が指数関数的に爆発してしまいます。

例えばfib(5)を実行すると、以下のように展開して計算されます。

   fib(5)
-> fib(4) + fib(3)
-> fib(3) + fib(2) + fib(2) + fib(1)
-> fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1
-> fib(1) + fib(0) + 1 + 1 + 0 + 1 + 0 + 1
-> 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
-> 5

展開中にfib(0)〜fib(3)を何度も呼び出しているのが分かると思います。
fib(1)なんかはトータルで5回も計算しています。
また、fib(6)を計算しようとすると、上記のfib(5)とfib(4)が呼び出され、さらに関数呼び出しの回数が増えてしまいます。

fib(30)とか計算しようとすると時間がかかりすぎて固まります。

動的計画法を使ってみた

というわけで、計算量を抑えた動的計画法版のfib(n)も定義してみました。
書いてみた結果がこれだよ。

fib <- function(n){
  if (n == 0) { return(0) }
  x <- numeric(max(n,2))
  x[1] <- x[2] <- 1
  m <- 3
  while (m <= n){
    x[m] <- x[m-1] + x[m-2]
    m <- m + 1
  }
  x[n]
}