关于快速幂算法

​ 所谓的快速幂算法就是进行快速幂运算的算法。它的思想可以看做是将一个幂运算拆分两个指数只差一的幂运算。

​ 例如n的2m次方，我们就拆成两个n的m次方。而n的2m+1次方，我们就拆成n的m次方和n的m+1次方。所以快速幂的时间复杂是O(log)。

​ 上面的思想我觉得比较容易去理解。快速幂还有一种解释。（其实和上面得差不多。但是如果要用非递归的思想去写模板的话那上面的想法就难实现了。）

​ 我们将所要进行幂运算的指数变为二进制形式。然后我们再用二进制转为十进制的思想进行幂运算。这里我就举一个具体的指数吧。n的13和18次方。13的二进制数为：(1101)。18的二进制数为(10010)。那么将(1101)变为13要进行下面的运算：20*1+21*0+22*1+23*1。即1+4+8，那么我们就可以把n的13次方看做是n*n4*n8（这里的指数也很特殊）。18也是一样的想法你可以自己转换一下。那对于我们来说我们只要每次判断指数二进制数中每位的数并让n每次都和自己相乘，当判断到其数为1的时候就将我们所要返回的数乘上此时的n就可以了。那么其时间复杂度也是O(log)

模板

递归函数实现

1
2
3
4
5
6
7
8
9
10
11
12
int quickPow(int n, int m) {
	if (m == 0)//除0以外的0次方都是1，因为0的0次方无意义所以就不管了
		return 1;
	if (m == 1)//任何数的1次方都是其本身
		return n;
	int tmp = quickPow(n, m/2);//这里调用递归
	tmp *= tmp;
	if (m % 2 == 0)//判断m是否为偶数
		return tmp;
	else
		return n * tmp;//不是的话，还要加上多余的n
}

非递归函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int quickPower(int n, int m) {
	if (m == 0)//除0以外的0次方都是1，因为0的0次方无意义所以就不管了
		return 1;
	if (m == 1)//任何数的1次方都是其本身
		return n;
	int ans = 1;
	while (m!=0)//当m为0的时候就是结束了
	{
		if ((m & 1)) {//这里用了位运算，判断当前位数是否为1
			ans *= n;//是就要乘上当前n的值
		}
		m = m >> 1;//进行右移运算，这样我们每次都能指向最新的位。并且这个可以成为一个标识去判断循环是否结束
		n *= n;//n与自己相乘
	}
	return ans;
}

​ 非递归函数的实现使用了许多进制运算但是实际上m&1也是判断m是否为奇数。m >> 1也就是m/2。至于为什么你们可以去了解一下进制运算。希望这篇文章能帮助到你。