快速幂运算

快速幂运算

一、反复平方 O(lgn)

一般求 pow(a, n) ，即 a 的 n 次幂，需要使用一个 for 循环来每次乘上一个 a，故时间复杂度为 O(n)。

这种方法中 a 的指数每次增长的步长为 1，在已知指数距离 n 还有一定距离的时候，为什么一步不跨大一点呢？

① 后来有人提出了反复平方的方法：

方法的核心就是每一次都乘以自身，那么 a 变成 a²，a²变成 a⁴，a⁴变成 a⁸……

这样一次的步长就是以 2 为指数的方法增长，因此时间复杂度为 O(lgn)。

但是每次跨的步长越来越大，要检查每次跨越之前检查是否会超过 n，

不超过就安全乘以自身，超过就将剩下部分再使用一个 pow(a, n-2ⁱ) 来乘上当前已经得到的 pow(a, 2ⁱ)。

② 还可以利用二进制，上图中的 pow(a, 10)，指数 n = 10 = (1010)₂，

这说明需要取 2³ = 8， 2¹ = 2，a⁸ * a² = a¹⁰。

因此我们可以用另一种策略：

从右往左一位一位地扫描 n 的二进制数，每扫过一位 a 就乘以自身，反复平方。

如果扫描的数为 1，则 ans *= a，如果为 0，则继续扫描。

扫描一遍之后 ans 就是最后的结果。

参考代码：

long long pow(int a, int n){
	long long ans = 1;
	long long pingfang = a;
	while(n != 0){
		if(n%2 == 1){
			ans *= pingfang;  // 遇到二进制中的1时 说明需要取 
		}
		pingfang *= pingfang;  // pingfang不断往上翻 
		n /= 2;
	}
	return ans;
}

二、斐波那契与矩阵幂运算 O(lgn)

斐波那契可以使用矩阵来直接求得，现在的重点是如何求得 n-1次幂的（0 1 1 1）矩阵。

一般的方法也可以在 O(n) 的时间复杂度来每次乘上一个 （0 1 1 1）矩阵来得到结果，

但是矩阵也可以像 pow(a, n) 一样进行快速幂。

矩阵幂运算 O(lgn)：

这里利用了 pow(a, n) 的第②种方法，若要求 pow(matrix, n)，matrix 是一个矩阵，

就把 n 用二进制表示出来，初始化单位矩阵 result。

每次 matrix 乘以自身，若扫到的二进制位为 1，则矩阵 result 就乘上矩阵 matrix，

这样就可以在 O(lgn) 的时间复杂度内得到矩阵 matrix 的 n 次幂。

参考代码：

// 矩阵的乘法
int **multiMatrix(int **matrix1, int **matrix2, int n){
	multiAns = new int*[n];
	for(int i = 0; i < n; i++){
		multiAns[i] = new int[n];
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			int sum = 0;
			for(int k = 0; k < n; k++){
				sum += matrix1[i][k]*matrix2[k][j];
			}
			multiAns[i][j] = sum;
		}
	}
	return multiAns;
}

// 矩阵快速幂
int** pow(int **matrix, int n, int k){
	// 初始化单位数组
    for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j){
				ans[i][j] = 1;
			}	
			else{
				ans[i][j] = 0;
			}
		}
	}
    // 复制一份matrix
	pingfang = new int*[n];
	for(int i = 0; i < n; i++){
		pingfang[i] = new int[n]; 
	} 
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			pingfang[i][j] = matrix[i][j];
		}
	}
    // 扫描二进制
	while(k != 0){
        // 若为1则乘上pingfang
		if(k%2 == 1){
			ans = multiMatrix(ans, pingfang, n);
		}
        // 无论是否为1都要乘以自身
		pingfang = multiMatrix(pingfang, pingfang, n);
		k /= 2; 
	}
	for(int i = 0; i < n; i++){
		delete[] pingfang[i];
	}
	delete[] pingfang;
	return ans;
}

【END】感谢观看