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

Given : 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 次平方和最多 log₂b 次乘法。

运行时间为O(log b)

---