c - 在 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

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

Answer 2

有关基本数学运算的问题和有关计算复杂性的问题，通常由 Wikipedia 快速回答。

求幂：积分幂的有效计算

一般来说，计算 bn 所需的乘法运算的数量可以通过使用平方取幂或（更一般地）加法链取幂来减少到 Θ(log n)。找到乘法的最小序列（指数的最小长度加法链）是一个困难的问题，目前还没有有效的算法（参见子集和问题），但有许多相当有效的启发式算法可用。

Answer 3

我们来分析一下：

power被调用（通过递归）的次数与原始y可被 2 整除的次数一样多（即最大数，k，使得2^k < y）。这意味着计算的次数大致为k=log_2(2^k)=log_2(y)~=log(y)，所以它是一个正确的答案。

“更好的方式”的答案取决于什么才是“更好”

Answer 4

这是执行此操作的方法：

假设你想要 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 为底写你的指数并得到所有相关的乘法

Answer 5

这里要快得多：%是一个非常昂贵的操作，用按位操作代替它是一个巨大的节省；也替换y/2为y>>1：

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