ソースは載せちゃやばいけど結果はあげても大丈夫だろうということで載せときます。ググったら結果はわんさか出てくるしね。というわけで得意技の(?)JFreeChartを使って出力。いや、やる必要ないんだけど、ただの趣味ですw
昨日言ってた指数的爆発。n=30越えると急に計算時間がアホみたいに増えます。
nの数字がしょぼくれちゃってますがnを一億から十億まで代入したときの計算量。
アルゴリズム1はを2くらいから地道に計算したやつ、2は行列を使って解いたやつ。行列のほうがいろいろやってるので時間はかかってるんですが、ほぼどちらも線形とみなすことができそうで、オーダーは同じと言えそうです。
フィボナッチ数の一般項もあったんで、それもやってみたんですが、n=1000000000(じゅーおく)くらいを代入しても計算時間がほぼ0という素晴しい結果。オーダーが違うとこうも違ってくるのか。
というわけで高校とかで解いてた漸化式を解くのはあながち無駄ではないようです。
