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