<分区>
面试问题:
Calculate x ^ y in O(log n)
有不同的答案，例如“使用 Indian Power 算法”或
double power(double x, int y)
{
if(y == 0) return 1;
double d = power(x, y/2);
if(y%2 == 0) return d*d;
else return x*d*d;
}
是正确答案吗？
有没有更好的方法来为这个问题编写代码？
<分区>
面试问题:
Calculate x ^ y in O(log n)
有不同的答案，例如“使用 Indian Power 算法”或
double power(double x, int y)
{
if(y == 0) return 1;
double d = power(x, y/2);
if(y%2 == 0) return d*d;
else return x*d*d;
}
是正确答案吗？
有没有更好的方法来为这个问题编写代码？
最佳答案
这叫做 Exponentiation by Squaring .就实现而言，这是一个品味问题。您的递归实现很好，但非递归实现(来自上面的链接)对于不喜欢递归或错误地认为它在某种程度上“浪费”或“缓慢”的人来说可能看起来更干净一些。
关于在 O(log n) 中计算 x ^ y，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10195252/