FXの自動売買とは

フィボナッチ数列の計算量について

フィボナッチ数列の計算量について

再帰アルゴリズム

再帰は、「n-1までが正しいと仮定したら、nの場合も正しいことを証明すれば、すべてのときに正しいといえる」という数学的帰納法と似た考え方です。nでの問題をn-1での結果を用いて解くアルゴリズムを考えればよいのです。
そのため、再帰アルゴリズムを用いることには、次のような利点があります。
・アルゴリズムを発見しやすくなる。
→プログラムが作りやすい。
・一般に、アルゴリズムが簡素になる。
→プログラムの誤りが少なくなる。
他人が読んでわかりやすいプログラムになる。
このような利点を実感するために、代表例として、「ソート」と「ハノイの塔」を後述します。

しかし、プログラムが簡潔であることは、必ずしも実行効率がよいことではありません。イのプログラムで f(5) をを実行するには、f(4),f(3),…,f(3) を実行しなければないません。関数を呼び出す回数が増加しますし、それらの結果を保存しておく必要があります。処理のための時間やメモリ容量は、むしろ増大してしまいます。その代表的な例として「フィボナッチ数列」を後述します。

配列aを小さい順にソートすることを考えます。これまでに、n-1個までは既にソートされているとき、要素a[n] について考えます。
1 2 3 フィボナッチ数列の計算量について n-1 n
┌──┬──┬──┬──┬──┐┌──┐
│10│20│40│50│60││a[i]│
└──┴──┴──┴──┴──┘└──┘

  1. a[n] の値30を一時的にwに保管しておきます。
  2. 配列の先頭から順にa[i] ≧a[n] の間iをずらしていき、a[i] <a[n] となる個所iを見つけます。(図ではi=3)
  3. 要素i~n-1を右に1つずらして、i+1~nに入れます。このとき右のほうからずらさないと、データが消えてしまいます。
  4. a[n] の値を保管していたwの値を a[i] に入れます。

ハノイの塔

かなり難解な問題が再帰を用いることにより、非常に簡単になる例として、「ハノイの塔」があります。
図のように、右の棒にn枚の円盤が積んであります。
・1回に1枚の円盤しか動かせない。
・小さい円板の上に大きい方の円盤を置いてはならない。
の規則に従って,円盤をAからBに移動せよという問題です。

プログラム 再帰を用いたプログラムは非常に簡単です。
ここでは円盤の小さい順に円盤番号nをつけています。

function hanoi(n, a, b, c) if (n==0) return;
hanoi(n-1, a, c, b);
document.write("円盤" + n + ": " + a + " → " + b + "
");
hanoi(n-1, c, b, a);
>

「hanoi(4, "左", "中", "右")」を実行した結果を示します。
ア 円板1: 左 → 右
イ 円板2: 左 → 中
ウ 円板1: 右 → 中
エ 円板3: 左 → 右
オ 円板1: 中 → 左
カ 円板2: 中 → 右 フィボナッチ数列の計算量について
キ 円板1: 左 → 右
ク 円板4: 左 → フィボナッチ数列の計算量について 中
ケ 円板1: 右 → 中 ─┐
コ 円板2: 右 → 左 │
サ 円板1: 中 フィボナッチ数列の計算量について → 左 │
シ 円板3: 右 → 中 │n=3
ス 円板1: 左 → 右 ─┐ │
セ 円板2: 左 → 中 │n=2 │
ソ 円板1: 右 → 中 ─┘ ─┘

円盤がn個あるとき、1~n-1の円盤を一つの円盤であるとして、1~n-1の円盤をP、n番目の円盤をQとすれば、2個の円盤を移動することだと考えることができます。
2つの円盤PとQがaの棒にあるとして、それをbの棒に正しく移動するには、次の3つの操作を行えばよいことは明白です(左中右などの物理的意味を排除するために、あえてa,b,cとします)。
操作1:PをAからCへ移動
操作2:QをAからBへ移動 フィボナッチ数列の計算量について
操作3:PをCからBへ移動

hanoi(m, a, b, c) とは、aからbへ移動することだと定義すれば、document.write(~)がそれにあたります。
そして、Pの移動とはn-1のときの移動のことですから、
操作1:hanoi(n-1, a, c, b);
操作3:hanoi(n-1, c, b, a);
となります。

フィボナッチ数列

再帰による処理効率の低下の例(再帰を使うべきではない例)として有名なのがフィボナッチ数列です。フィボナッチ数列とは、
1,1,2,3,5,8,13,21,…
の数列で、1+1=2,1+2=3,2+3=5のように、直近の2つの数を加えたものです。それで、
┌1 (n=1のとき)
F(n)=│1 (n=2のとき) フィボナッチ数列の計算量について
└F(n-1) + F(n-2) (n≧3のとき)
と定義できます。

再帰を用いないならば、1つ前の数をx1,2つ前の数をx2として、プログラムf1にすることができます。
function f1(n);
if (n
となります。

再帰を用いたプログラムf2は、
function f2(n);
if (n
となります。

計算量を forループ のなかの3つで代表させるならば、f1での計算回数は、3n回です。
それに対してf2の計算回数は、ほぼフィボナッチ数列での値と同じ程度の回数になります。
nが大きい場合、例えばn=30のときでは、f2ならば90回なのに、f1では(n=30のフィボナッチ数は)832,040回になってしまいます。

関連記事

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次
閉じる