在O(log n)中计算x ^ y

Question

面试问题:

在O(log n)中计算x ^ y

有不同的答案,如"使用印度力量算法"或

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;
}

1. 这是一个正确的答案吗？

2. 有没有更好的方法来编写这个问题的代码？

Answer 1

这被称为Squaring的Exponentiation.就实施而言,这是一个品味问题.你的递归实现是好的,但非递归实现(来自上面的链接)对于那些不喜欢递归或者错误地认为它在某种程度上"浪费"或"慢"的人来说可能看起来更清晰.