算法提高 第一课——快速幂

什么是快速幂

顾名思义，快速幂就是快速算底数的 $n$ 次幂。其时间复杂度为 $O(lo{g}_{2}N)$， 与朴素的 $O(N)$ 相比效率有了极大的提高。

原理分析

快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。

例如：
$$3^{10}=3\ast 3\ast 3\ast 3\ast 3\ast 3\ast 3\ast 3\ast 3\ast 3$$
$$3^{10}=(3\ast 3)\ast (3\ast 3)\ast (3\ast 3)\ast (3\ast 3)\ast (3\ast 3)$$
$$3^{10}=(3\ast 3{)}^5$$
$$3^{10}=9^5$$
$$9^5=9^4\ast 9^1$$
$$9^5=6561^1\ast 9^1$$

因为是求 $a^b$ ，所以可以把b转换成二进制数。则这个二进制数第 $i$ 位的权为 $a_{i-1}$，例如：
$$当b=11$$
$$a^{11}=a^{2^0}+a^{2^1}+a^{2^3}$$
$$11的二进制为1011$$
$$11=2^3\times 1+2^2\times 0+2^1\times 1+2^0\times 1$$
所以，$a^{11}$ 转换为：$a^{2^0}+a^{2^1}+a^{2^3}$

代码实现

我们可以直接用位运算来实现。

STEP1

既然是位运算，那么就需要将 $b$ 转换为二进制。则：

int qmi(int a,int b)//求a的b次方
{
	//STEP1
	int res=1;//用来记录最后的值
	while(b)
	{
		b>>=1;
	}
	
	return res;
}
1
2
3
4
5
6
7
8
9
10
11

STEP2

根据上文分析，我们得知：每次的 $b$ 均需 &1，判断其这一位是否为1,。若是1，则 $res=res\times a$。否则不运算（即乘0）。记得，每次判断后 $a$ 均要将指数加 $1$。代码如下：

int qmi(int a,int b)//求a的b次方
{
	//STEP1
	int res=1;//用来记录最后的值
	while(b)
	{
		//STEP2
		if(b&1)
		{
			res=res*a;
		}
		a=a*a;
		
		b>>=1;
	}
	
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

总结

快速幂也没什么难点，就算不理解，也能将其背下来。也许，硬背和理解的唯一不同就是你根本不知道这个函数为什么要位运算。