-4

次のコードの再帰関数を作成する方法はありますか?

for(int i=0; i<1000000; i++){
    for(int j=0; j<1000000; j++){
        for(int k=0; k<1000000; k++){
            //Do something using i,j and k
        }
    }
}

考えられるすべての数列を組み合わせる必要があります。例: (0,0,0) (0,0,1) (0,1,0)

このループを通過するのに約10時間かかったので、単純化する必要があり、再帰関数でそれができると思います。

ありがとう

4

3 に答える 3

3

理論的には、すべての反復ループを再帰呼び出しに変換できます (無限スタックまたは末尾呼び出しを使用)。

  1. 再帰は反復よりも高速ではありません- 時間の複雑さは同じです
  2. Java はTCOをサポートしていないため、そのような深い再帰呼び出しをサポートしていません - 数十: はい、数百万: 絶対にありません。

この場合、途方もない回数ループするため、長い時間がかかります。ブルート フォース アルゴリズムは O(n c ) です。ここで、c は 3 です。つまり、境界は多項式時間であり(これは適切ではありません)、n は「比較的大きい」です。それは多くの無駄な CPU サイクルです。

とにかく、この多くの順列を直接使用/保存するのは一般的に正気ではないことを考えると、元の問題を再検討し、合理的な時間の複雑さでアプローチを導き出すことが有益かもしれません。たとえば、順列を数えるためのはるかに優れた方法があります..

于 2013-03-26T05:01:56.663 に答える
1

なぜそれを再帰的に変換すると、実行が遅くなります..

しかし、これを試すことができます：

public static void recursiveLoop (int i, int j, int k, int w, int h, int d)
{

    /* code .. */

    /* increment i,j,k */
    if (k == d)
    {
        k = 0;
        j++;
    }

    if (j == h)
    {
        j = 0;
        i++;
    }

    if (i == w)
    {
        return; // Stop
    }

    recursiveLoop(i,j,k);

}

しかし、コンパイラはそれを次のように変更します。

public static void recursiveLoop (int i, int j, int k, int w, int h, int d)
{

    do
    {

        /* code .. */

        /* increment i,j,k */
        if (k == d)
        {
            k = 0;
            j++;
        }

        if (j == h)
        {
            j = 0;
            i++;
        }

    }while (i != w);

}
于 2013-03-26T05:55:42.017 に答える
0

次の再帰について考えてみましょう。詳細については、これを参照してください。 再帰はループよりも高速ですか?

したがって、Java にタグを付けたように、スタック メモリを割り当てる必要があるため、再帰は反復よりもコストがかかります。したがって、それらの順列を記録することが意図されている場合は、後で使用するためにそれらをファイルに保存することをお勧めします。そして、これに対するより正確な答えを指定できる問題のステートメントに依存します。

于 2013-03-26T05:30:56.437 に答える