実行時間
1. 再帰関数の実行
ここは演習を交えながら説明しよう。
演習 1. フィボナッチ数
を満たす数列 を、フィボナッチ数列と呼ぶ。
フィボナッチ数の第項を求める関数を、定義に沿って再帰関数によって実装し、 を求めよ。
である。
コード解答
#include <iostream>
using namespace std;
int fib(int n) {
if (n==1 || n==2) return 1;
return fib(n-1) + fib(n-2);
}
int main() {
cout << fib(20) << endl;
}しかし、この関数を使って は求めようとすると実行にかなり時間がかかり、 の計算は完了しなくなる。なぜだろうか？
演習 2. フィボナッチ関数
演習 1. で実装した関数を「フィボナッチ関数」と呼ぶ。第項を求める時に、フィボナッチ関数は総計で何回実行されるか。
解答
答えは 9 回である。
証明は数学的帰納法による。 は fib を1回実行する。以下、fib の実行回数を とする。fib(3) は fib(2) fib(1) を呼び出すが、それぞれの中で fib は呼ばれず、合計 回呼び出される。 fib(3) を呼び出す回数も含めて、 。
同様に、 。
よって、 。
この結果から、この関数で呼び出される fib の回数は、大体 回くらいだと考えられる。
TIP
この「大体」というのは少しむずかしい。
が十分大きいとき fib が呼ばれる回数 と はおおよそ比例関係になる。 つまり、 を正の無限大に飛ばしたときに、 は正の有限値に収束する。 このとき、計算機科学的にはざっくり同じくらいの計算回数だと捉えられ、ここでは「大体」という言葉で説明される。
もし気になったのなら、「オーダー記法」「ランダウの記号」について調べると良い。余裕があれば第8章にて説明する。
コンピューターは人間よりもずっと高速に計算できるが、無限に早く計算できる訳ではない。目安として、1秒に大体 ～ 回の計算ができる。 なので、大体10秒はかかる。 に関しては更に時間がかかるだろう（おそらく5分ほど）。
「コンピューターは人間よりもずっと高速に計算できるが、無限に早く計算できる訳ではない」という事さえ頭の中に入れておけば、とりあえず問題ない。
2. 再帰関数の改善
このプログラムを TSUBAME に投げれば数秒で返ってくるかもしれない（実際はこのままだと返ってこないのだが…）。
しかし、そもそも自分の手で を計算する際に、足し算を9回も行っているだろうか？ 実際は足し算は多くて5回ではないだろうか。 の計算も、たかだか50回の足し算さえすればよく、頑張れば5分以内に計算できる。
こうなっては人間の方が計算速度が早いということになるが、冷静に考えてそんな訳はない。
ここで、自分たちが実際に行った計算方法を思い返して、それをプログラムに落とし込めば高速に計算できるのではないだろうか。
演習 3. フィボナッチ関数の高速化
手計算での方法を思い出しながら、フィボナッチ数を計算するプログラムを実装し、 を高速に（1秒以内に）計算せよ。
ヒント 1
例えば は、 と の情報さえあれば計算できる。
ヒント 2
for 文を使って、 から順番に計算して、その計算結果を記憶すれば何度も計算せずに済む。
ヒント 3
例えばフィボナッチ数列を記憶する変数 vector<int> fibo を用意してみたらどうだろうか。 for 文の中では何番目かを表す があるから、 等すれば前のフィボナッチ数が取得できる。
解答コード
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> fibo = {0, 1, 1};
int n = 0;
cin >> n;
if (n <= 2) {
cout << fibo[n];
return 0;
}
for (int i=3; i<=n; i++) {
int ai = fibo[i-1] + fibo[i-2];
fibo.push_back(ai);
}
cout << fibo[n] << endl;
}