c++ - 在 O(1) 中计算幂函数

Question

我写了一个函数来计算 O(logb) 中的 pow(a,b)。

double pow(double a, int b){
  double res=1;
    while(b>0){
        if (b%2==1){
            res=res*a;
        }
      b=b>>1;
      a=a*a;

    }
    return res;
}

我偶然发现了是否可以及时编写函数 pow(double a, double b) 的问题O(1)。然而我还没有找到答案。

标签： c++algorithmmath

Answer 1

如果您不允许自己使用标准 pow/exp/log 函数或预计算表，但允许浮点乘法，那么您的解决方案是最佳的（恒定时间是不可能的）。