权力的时间复杂度()

Question

我实现了这个功能,power()这需要两个参数a和b并计算^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

Squaring的指数.

非递归实现

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 squarings并且最多log ₂ b乘法.

运行时间为O(log b)

Answer 2

通过平方使用指数

Answer 3

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