快速幂算法

September 30, 2017

在c，c++语言中，并没有提供求幂的基本运算，通常我们需要自己写函数或者调用STL提供的函数。

一般情况下，我们写的求幂函数基本上都是循环累乘，时间复杂度为O(n)。虽说是线性的时间复杂度，但求幂运算作为基础运算，往往调用频繁，这时候即使是线性的时间复杂度也将变得难也接受。

利用快速幂可以快速计算底数的n次幂。其时间复杂度为 O(logn)

原理 #

以求 $a^{11}$ 为例，将11写成二进制形式 1011。

则 $a^{11} = a^{2^0+2^1+2^3}=a^{1+2+8} =a^1\times a^2\times a^8$

使用一个累乘器，每次翻倍 base = base*base 逐步得到 $a^1,a^2,a^4,a^8$ ，根据11的二进制，如果为1则乘进结果里。

实现 #

迭代算法

int power(int a,int b)
{
	int base = 1,ans = a;
    while(a > 0){
        if(a & 1 == 1) ans *= base;//二进制位为1的才要乘
        base *= base;
        a >>= 1;
    }
    return ans;
}

递归算法

int power(int a,int b)
{
	if(b == 1) return a;
  	int temp = power(a,b>>1) * power(a,b>>1);
    return (b&1 == 1 ? a:1) * temp * temp;
    // 若指数为偶数则分解成一半，若为奇数，则还要再乘a
}

递归算法与迭代算法的思路略有不同。