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 方法进行了两次调用：

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)

在每次迭代中，您创建的问题的大小只有问题的一半（这很好），但您正在创建其中两个。

你应该这样做，而不是

 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 回答