0

フィボナッチ行を 2 つの異なる方法で計算します。fib1 が fib2 よりもはるかに長く実行されるのはなぜですか?

public class RecursionTest {

    @Test
    public void fib1() {
        long t = System.currentTimeMillis();

        long fib = fib1(47);

        System.out.println(fib + "  Completed fib1 in:" + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();

        fib = fib2(47);

        System.out.println(fib + "  Completed fib2 in:" + (System.currentTimeMillis() - t));

    }


    long fib1(int n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            return fib1(n - 1) + fib1(n - 2);
        }
    }


    long fib2(int n) {
        return n == 0 ? 0 : fib2x(n, 0, 1);
    }

    long fib2x(int n, long p0, long p1) {
        return n == 1 ? p1 : fib2x(n - 1, p1, p0 + p1);
    }
}

出力：

2971215073  Completed fib1 in:17414
2971215073  Completed fib2 in:0
4

4 に答える 4

6

両方のアルゴリズムの動作がまったく異なるためです。これを fib(5) で示しましょう。

fib1(5) を呼び出すと、内部的に fib1(4) と fib1(3) が呼び出され、ツリーで視覚化できます。

    fib(5)
  / \
fib(4) fib(3)

現在、fib(4) は内部的に fib(3) と fib(2) を呼び出しています。

これで、次のようになりました。

           fib(5)
          / \
    fib(4) fib(3)
    / \ / \
fib(3) fib(2) fib(2) fib(1)

これがどこに向かっているのかは今では非常に明白だと思います。残りを埋めることができるはずです。

edit : ここで注意すべきもう 1 つの点は、実際には同じ計算を複数回実行する必要があることです。この図では、 fib(2) と fib(3) の両方が複数回呼び出されています。そして、開始数が大きくなると、これはさらに悪化します。/編集

それでは、fib2(5) を見てみましょう。0 で呼び出すと、0 が返されます。それ以外の場合は、fib2x(n, 0,1) が呼び出されます。fib2x(n, 0,1) は内部で fib2x(n-1, p1, p0+p1) などを呼び出します。それでは、見てみましょう：

        
fib2x(5, 0,1) => fib2x(4, 1,1) => fib2x(3, 1, 2) => fib2x(2, 2, 3) => fib2x(1, 3, 5)

それまでにリターン条件に達し、5 を返します。

したがって、アルゴリズムはまったく異なる働きをします。最初のものは再帰的に、上から下に動作します。2 つ目は 1 から始まり、上に向かって進みます。実際には、再帰的というよりも反復的です (おそらく再帰的に書かれたのは、あなたをうんざりさせるためです)。すでに計算された値を破棄するのではなく保持するため、呼び出す必要のある計算がはるかに少なくなります。

于 2012-06-07T17:30:50.860 に答える
5

その理由は、2 つのアルゴリズムの実行時の複雑さが異なるためです。

于 2012-06-07T17:15:39.290 に答える
3

最終的には、末尾再帰fib2のみを使用するためです。最後に再帰呼び出しを1回だけ行います。したがって、再帰に関連する「分岐」はなく、線形時間ソリューションにつながります。これが末尾呼び出しであるという事実は、再帰をより低いオーバーヘッドで反復プロシージャに変換できる特定のコンパイラ/VMの最適化にもつながります。

fib1末尾呼び出しに加えて別の再帰呼び出しを使用します。これにより、実行時間が指数関数的になります。

于 2012-06-07T17:37:12.180 に答える
2

fib1 は O(2^n) ランタイムのアルゴリズムです。fib2 は O(n) ランタイムのアルゴリズムです。

この理由は非常にクールです。メモ化と呼ばれる手法です。プログラムが行う作業は各ステップで保存され、不要な計算が回避されます。

ループをさらに数ステップ展開すると、それが発生することがわかります。

long fib2(int n) {
    return n == 0 ? 0 : fib2x(n, 0, 1);
}
long fib2x(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xy(n - 1, 1, 1);
}
long fib2xy(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xyz(n - 1, 1, 2);
}
long fib2xyz(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xyz(n - 1, p1, p0 + p1);
}

このループをフィボナッチ数列の任意の数に展開できます。各ステップは、n が使い果たされるまで、スタックに以前に保存された計算に基づいて構築されます。これは、すべてのステップでこの作業をやり直さなければならない最初のアルゴリズムとは対照的です。気の利いた！

于 2012-06-07T17:33:19.080 に答える