在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. 有没有更好的编写此问题代码的方法？

- Elnaz

---

不，这是一个面试问题，你可以看到标签;) - Elnaz

else 是多余的。 - Gilad Green

Answer 1

这被称为平方取幂算法。就实现而言，这是一个品味问题。你的递归实现很好，但非递归实现（来自上面的链接）可能看起来更加简洁，对于那些不喜欢递归或错误地认为它在某种程度上是“浪费”或“慢”的人来说。

- Sergey Kalinichenko

Answer 2

对于基本的数学运算和计算复杂度的问题，通常可以在维基百科上快速找到答案。

指数运算：整数幂的高效运算方法

一般来说，使用平方法或加链指数运算法可以将计算bn所需的乘法操作次数降至Θ(log n)。寻找最小的乘法序列（即指数的最短加法链）是一个困难的问题，目前还没有有效的算法解决（参见子集和问题），但许多相当有效的启发式算法可供选择。

- Potatoswatter

Answer 3

以下是实现方法：

假设你想算2的1024次方，只需要进行11次乘法操作。

具体做法如下：

2*2 = 2^2
2^2 * 2^2 = 2^4
2^4 * 2^4 = 2^8
2^8 * 2^8 = 2^16
....
2^512 * 2^512 = 2^1024

基本上，您只需要将指数用2为底写出，并获取所有相关的乘法。

- scibuff

Answer 4

让我们来分析一下：

power 通过递归调用的方式被调用，调用次数等于原始 y 可以被 2 整除的次数（也就是最大的数字 k，使得 2^k < y）。这意味着计算次数大约为 k=log_2(2^k)=log_2(y)~=log(y)，因此这是一个正确的答案。

“更好的方法”的答案取决于什么被视为“更好”。

- Attila

Answer 5

这里更快：使用按位运算替换 % 可以大大减少开销；还可以用 y>>1 替换 y/2：

double power(double x, int y) {
    if(y == 0) return 1;

    double d = power(x, y>>1);

    if((y&1) == 0) return d*d;
    else return x*d*d;
}

- kasavbere

---

你有通过性能剖析验证性能改进吗？x%2通常会被优化为x&1，同样地，x/2和x>>1也是如此。微观优化不是一个好主意，除非你正在解决实际阅读反汇编代码时发现的问题。所有这些只是使用了错误的运算符，使优先级规则更加混乱。例如，(y&1 == 0)不会做你以为它做的事情。 - Potatoswatter

虽然我完全同意@Potatoswatter的观点，但我想补充一下，if(y&1)也是可能的（尽管在某些代码风格中不好）:D - SOFe

另一方面，在某些情况下，写>> 1比/ 2更明显，甚至具有不同的语义，例如在PHP中，/执行浮点除法而>> 1将操作数转换为整数。 - SOFe