8

私はプロジェクト Euler を進めていましたが、組み合わせの問題に遭遇しました。組み合わせロジックとは、階乗を計算することを意味します。そこで、factorial メソッドを作成することにしました。そして、問題にぶつかりました - これを行うために反復と再帰の両方を非常に簡単に使用できるため、どちらを使用する必要がありますか? 私はすぐに2つの方法を書きました-反復:

public static long factorial(int num) {
        long result = 1;
        if(num == 0) {
            return 1;
        }
        else {
            for(int i = 2; i <= num; i++) {
                result *= i;
            }
            return result;
        }

そして再帰的：

public static long factorial(int num) {
        if(num == 0) {
            return 1;
        }
        else {
            return num * factorial(num - 1);
        }
    }

ここで (明らかに) 速度と機能について話している場合、どちらを使用する必要がありますか? そして、一般的に、どちらかのテクニックが他のテクニックよりも一般的に優れているのでしょうか?

4

4 に答える 4

15

どちらも絶望的にナイーブです。階乗の深刻な適用では、どちらも使用しません。どちらもn が大きい場合は非効率的であり、引数が大きい場合はどちらも十分ではないと思いintますlong。

より良い方法は、適切なガンマ関数の実装とメモ化を使用することです。

これは Robert Sedgewick による実装です。

大きな値には対数が必要です。

于 2012-06-23T17:55:30.667 に答える
1

私は実際にこの問題を時間要因で分析していました。私は2つの簡単な実装を行いました:

反復:

private static BigInteger bigIterativeFactorial(int x) {
    BigInteger result = BigInteger.ONE;
    for (int i = x; i > 0; i--)
        result = result.multiply(BigInteger.valueOf(i));
    return result;
}

そして再帰的：

public static BigInteger bigRecursiveFactorial(int x) {
    if (x == 0)
        return BigInteger.ONE;
    else
        return bigRecursiveFactorial(x - 1).multiply(BigInteger.valueOf(x));
}

シングルスレッドで実行されている両方をテストします。引数が小さい場合のみ、Iterative の方がわずかに高速であることがわかります。n を 100 より大きくすると、再帰的なソリューションの方が高速でした。私の結論？JVM では、反復ソリューションが再帰ソリューションよりも高速であるとは言えません。(まだ時間の話だけ)

あなたが興味を持っているなら、私がこの結論を得る方法はここにあります

この 2 つのアプローチの違いをより深く理解することに興味がある場合は、knowledge-cess.com で非常に優れた説明を見つけました。

于 2016-07-09T10:30:05.547 に答える