Help us understand the problem. What is going on with this article?

フィボナッチ数列を計算する

計算量について考えるネタとして、フィボナッチ数列を取り上げます。なお、多倍長整数など環境的にちょうどいいのと、作者が慣れているという理由で、コードはRubyで書きます。

いちおう、紹介

改めて説明するまでもないかもしれませんが、フィボナッチ数列とは以下のようなものです1

$F_1 = F_2 = 1,\ F_{n + 2} = F_n + F_{n+1}\ (n \ge 1)$

具体的に書き出すと、1、1、2、3、5、8、13、21のようになります。

ナイーブに実装

いちばんシンプルにやるなら、定義どおりに再帰的に実装することも可能です。

def fib(n)
  return 1 if n <= 2
  fib(n - 1) + fib(n - 2)
end

もちろんこれでも実行はできますが、文字通りねずみ算式にfibを呼び出し続けるため、計算量は $O(2^n)$ となってしまいます2。大きい数については実用的ではありません。

メモ化を行う

いちばんシンプルには、すでに計算した分をメモ化すれば、残りの計算が不要となるので、計算量は $O(n)$ まで下がります2

Rubyの場合、ブロックつきHashを使えば、物凄くシンプルにメモ化を書けます(参考)。

fib = Hash.new do |h, n|
  if n <= 2
    1
  else
    h[n] = h[n-1] + h[n-2]
  end
end

一般項で計算する

$x^2 + x - 1 = 0$ の解となる $\phi = (-1 +\sqrt{5})/2$ という値を使うと、$\phi(1 + \phi) = 1$ なので、漸化式は以下のように書き直せます。

\begin{align}
F_{n + 2} &= F_{n+1} + F_n \\
F_{n + 2} + \phi F_{n + 1} &= (1 + \phi)F_{n+1} + F_n\\
&= (1 + \phi)(F_{n+1} + \phi F_n)\\
&= (1 + \phi)^{n} (F_2 + \phi F_1)\\
&= (1 + \phi)^{n+1}
\end{align}

同様に、 $\phi' = (-1 -\sqrt{5})/2$ についても、 $F_{n + 2} + \phi' F_{n + 1} = (1 + \phi')^{n+1}$ となります。よって、この2式から $F_{n + 2}$ を消去して、

\begin{align}
(\phi - \phi') F_{n+1} &= (1 + \phi)^{n+1} - (1 + \phi')^{n+1} \\
F_{n+1} &= \frac{(1 + \phi)^{n+1} - (1 + \phi')^{n+1}}{\phi - \phi'}\\
&= \frac{1}{\sqrt{5}}\left\{\left(\frac{1 + \sqrt{5}}{2}\right)^{n+1} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n+1}\right\}
\end{align}

さらに、 $((1 - \sqrt{5})/2)^n / \sqrt{5}$ の項の絶対値は0.5以下なので、1項目だけ計算して四捨五入すれば正しい値が出ます。

もっとも、大きなフィボナッチ数を計算する場合、概数はこれで見積もれますが、大きな数の計算精度に限界があるので、1の位まで正確な値を出すには向かない方法です。

行列で計算する

フィボナッチ数列の漸化式を行列で表すと、以下のようになります。

\begin{pmatrix}
F_{n + 1} \\ F_n
\end{pmatrix} = 
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} 
\begin{pmatrix}
F_{n} \\ F_{n - 1}
\end{pmatrix} 

ということで、繰り返し展開を続けると、

\begin{pmatrix}
F_{n + 1} \\ F_n
\end{pmatrix} = 
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n - 1}
\begin{pmatrix}
F_{2} \\ F_{1}
\end{pmatrix} 

となります。あとは行列の冪を計算するだけですが、これは $O(\log n)$ で片付きます2

require 'matrix'

base = Matrix[[1, 1], [1, 0]]

p base ** 10

  1. 0からスタートする流儀と1からスタートする流儀があるようです。 

  2. 厳密にいえば、桁数が増えると加算・乗算の計算量自体も増えていきますので、このとおりではないです。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away