algorithm - 使用分而治之算法的力量

Question

我想找出计算 X^46 时，使用最佳 D&C 方法计算 Power 时发生了多少次乘法运算。

我认为这是使用分治法计算功率的最佳代码。

int power(int x, unsigned int y)
  {
     int temp;
     if( y == 0)
       return 1;
     temp = power(x, y/2);
     if (y%2 == 0)
       return temp*temp;
     else
       return x*temp*temp;
  }

在一篇为在 D&C 中使用最佳幂代码计算 X^46 而写的注释中，我们需要 8 次乘法，但在我的代码中有 10 次。有人纠正我吗？

编辑:

最后的代码是:

  int power(int x, unsigned int y)
  {
     int temp;
     if( y == 0)
       return 1;
     if( y ==1)
        return x;
     temp = power(x, y/2);
     if (y%2 == 0)
       return temp*temp;
     else
       return x*temp*temp;
  }

Answer 1

您遗漏了

的优化基本情况

 if (y==1)
     return x

而是需要额​​外的乘法运算

 temp = power(x, 0)
 return x * temp * temp

额外的一对乘法来自不必要的最终递归调用。