power() 的时间复杂度

Question

我实现了这个函数 power()，它接受两个参数 a 和 b 并计算 a^b。

typedef long long int LL;

LL power(int a,int b)
{
   int i = 1;
   LL pow = 1; 
   for( ; i <= b ; ++i )
     pow *= a;
   return pow;
}

给定：a^b落在long long int范围内。
问题：如何降低算法的时间复杂度？

Answer 1

通过平方求幂。

非递归实现

LL power(int a, int b)
{
  LL pow = 1;
  while ( b ) 
  {
         if ( b & 1 ) 
         {
           pow = pow * a;
           --b;
         }
         a = a*a;
         b = b/2;
  }
  return pow;
}

该算法需要 log₂b< /strong> 平方和最多 log₂b 乘法。

运行时间O(log b)

---

Answer 2

使用通过平方求幂

Answer 3

通过平方求幂并不能在所有情况下给出最小乘法次数。寻找“加法链”、“布劳尔链”、“汉森链”和“肖尔茨猜想”。

Answer 4

我建议：如果您确实需要更快的函数（使用 long double ），请使用 pow() 函数，或者自己考虑一下您的作业。

对于任意精度：请参阅 GMP 库
http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation

Answer 5

使用平方求幂。也就是说，如果我们需要a^b，我们检查b是否是偶数，如果b是偶数，我们找到(a^2)^(b/2)，否则我们找到a* ((a^2)^(b/2))。这可能不是最好的算法，但它比线性算法更好。

int Power(int a, int b)
{
    if (b>0)
    {
       if (b==0)
          return 1;
       if (a==0)
          return 0;
       if (b%2==0) {
          return Power(a*a, b/2);
       }
       else if (b%2==1)
       {
        return a*Power(a*a,b/2);
       }
    }
    return 0;
}

Answer 6

下面是Java代码的递归实现
使用 通过平方求幂 计算 2 的 n 次方，复杂度为 O(log n)

int ans=1;
public int myTwoPower(int n){
    if(n<=0)
        return 1;

    if(n%2 !=0){            
        return myTwoPower(n-1)*2;
    }
    else{
        ans = myTwoPower(n/2);
        return ans * ans;
    }
}