3

2^8 を再帰的に計算しようとすると、このメソッドが 31 回使用される方法がわかりません。

このメソッドは、O(logN) の複雑さでべき乗を計算しますか?

実行すると、出力は次のようになります。

0
1
2
3
4
5
...
29
30
2^8 is: 256

コード

private static int power(int x, int y)
{
    System.out.println(step++);

    if (y == 0)
        return 1;

    return power(x, y/2) * power(x, y/2);
}
4

4 に答える 4

6

ここでは、同じ値で power メソッドを 2 回呼び出しています。

return power(x, y/2) * power(x, y/2);

代わりに、次のように記述すれば、半分の呼び出しを行うことができます。

int toReturn = power(x, y/2);
return toReturn * toReturn;

元の例を見ていくと、31 回の呼び出しが行われます。これは、表示されているとおりです (0 から 30)。コードを見て、理由を確認してください。

power(2, 8)

power(2, 4)
power(2, 4)

power(2, 2)
power(2, 2)
power(2, 2)
power(2, 2)

power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)

power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
于 2012-10-26T07:38:11.127 に答える
2

他のポスターが指摘しているように、powerメソッドを頻繁に呼び出しています。再帰のレベルをカウントするために静的変数を使用することはお勧めしないことを追加したいと思います (これをコメントとして行いたくありません)。代わりに、現在のステップを別のパラメーターとして関数に渡すことをお勧めします。

private static int power(int x, int y, int recursiveCallStep)
{
    System.out.println(recursiveCallStep++);

    if (y == 0)
        return 1;

    int toReturn = power(x, y/2, recursiveCallStep);
    return toReturn * toReturn;
}

最初の呼び出しは次のようになります。

int result = power(2, 8, 0);

以前にこれを行っていれば、同じステップ番号が複数回出力されることに気付いたでしょう。

于 2012-10-26T07:59:43.410 に答える
1

いいえ、O(logN) ではありません。O(NlogN) です。

各反復で、問題の半分のサイズの問題を作成していますが (これは良いことです)、そのうちの 2 つを作成しています。

代わりに、あなたはすべきです

 return power(x, y/2) * power(x, y/2);

これ

 int power = power(x, y/2);
 return power * power;
于 2012-10-26T07:39:49.840 に答える
0

ディバイド エ インペラ ツリーはまったく必要ありません。これが、コードが同じ値を複数回再計算している理由です。

この単純な再帰コードを使用すると、はるかに複雑になります (O(N) であることがわかります)。

private static int power(int x, int y)
{
    System.out.println(step++);

    if (y == 0)
        return 1;
    else
    {
        return x * power(x, y - 1);
    }
}

X = 2 および Y = 3 の場合、スタック トレースは次のようになります。

power(2,3) = 2 * power(2, 2);
power(2,2) = 2 * power(2, 1);
power(2,1) = 2 * power(2, 0);
power(2,0) = 1;
于 2012-10-26T08:11:15.283 に答える