什么是快速幂,为什么要使用快速幂?
> Macw: 快速幂有好多好处。
> Penelope: 例如?
> Macw: 它比较快。
见名知意,快速幂算法可以在非常短的时间内求出一个数的 nnn 次幂。虽然快速幂在初学阶段的应用不算太多,但是快速幂背后的思想是非常值得我们去理解的。
举例而言,如果我们要求出 343^434 的值是多少?我们当然可以暴力求解 3×3×3×3=813 \times 3 \times 3 \times 3 = 813×3×3×3=81。如果要求出 3n3^{n}3n 是多少呢?暴力也还不为过...
暴算法力求解一个数的次幂的时间复杂度是 O(n)O(n)O(n)。如果我们要求解的次幂非常高的时候,那么速度就会变得非常慢。众所周知,普通64位测评机每秒也就能处理 10810^8108 左右的数据。因此我们需要找到一个更优的算法来解决这个问题。
快速幂算法的核心思想就是幂运算的乘法法则。
我们以求 3163^{16}316 为例,根据“同底次幂相乘,底数不变,指数相加的法则”,我们可以把问题看作成求解 38×383^{8} \times 3^{8}38×38 的值。不难看出,这样的话我们只需要知道 383^838 的值,我们就可以快速求出 3163^{16}316 的值了,不再需要在 383^838 的基础上再乘 888 遍来得到最终结果。相同地,我们也可以以同样的方法快速求出 383^838 的值,这样子程序运行的速度将会大大减少:
再以计算 3163^{16}316 次方为例:
1. 我们先计算 323^232 的值。
2. 然后就可以立刻计算出 343^434 的值。
3. 然后就又可以计算出 383^838 的值。
4. 最后就能快速地计算出 3163^{16}316 的值了。
比较新的快速幂的算法和普通的暴力算法,可以看到原本需要运行 161616 次的乘法运算现在只需要运算 444 次就可以计算出答案了。当数据量越大的时候,两个算法的速度差距就会越明显。(稍微学过初高等数学的人可以推断出快速幂算法的时间复杂度约为 O(log2(n))O(log_2(n))O(log2 (n)),对数时间复杂度远优于线性时间复杂度)。
快速幂算法的进一步拓展
然而,大家也都发现了,普通的快速幂算法只能解决要求解次幂为 222 的指数的情况(将代码稍做修改其实也可以解决所有以偶数作为次幂的情况)(例如:1,2,4,8,…,2n1, 2, 4, 8, \dots, 2^n1,2,4,8,…,2n)。难道对于那些非 222 的指数倍的次幂就没有办法了吗?当然不是。
我们都知道,任意一个数字都可以被查分成多个 222 的次幂的和。
例如数字 343434,可以写成二进制形式 100100(Base 2)100100_{(Base\space2)}100100(Base 2) 。那么 323232 这个数字就可以被分解成 25+222^5 + 2^225+22。再根据幂运算的乘法法则,若要计算出任意数字 x34x^{34}x34,只需要计算出 x25x^{2^5}x25 和 x22x^{2^2}x22,即 x32x^{32}x32 和 x4x^{4}x4 就可以再按照之前的快速幂方法快速求解答案。
因此,对于求任意一个指数非 222 的次幂的值,我们可以将这个指数分解成多个 222 的次幂相加的和并依次求解出最后的答案即可。其中,这多个 222 的次幂的数字我们也可以通过普通的快速幂算法快速求得答案。
到目前为止,快速幂算法就迎刃而解了。
快速幂算法的代码以及实现
这个是 C++ 代码的快速幂模版:
这段代码通过递归求解问题,将一个大的次幂转变成两个小的次幂的积进行运算。
这个是经过位运算优化过后的快速幂模板:
矩阵快速幂 - 结束语
学过线性代数的同学们看过来!
快速幂算法不光可以求解普通的快速幂问题,我们还可以用同样的方法对一个任意大小的矩阵求快速幂。快速幂在矩阵乘法中的作用非常的大,普通的两个矩阵相乘的时间复杂度约为 O(n3)O(n^3)O(n3),其中 n×nn \times nn×n 为矩阵的大小。
Matrix=[a1,1a1,2a1,3a2,1a2,2a2,3a3,1a3,2a3,3]nMatrix = \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix}^n Matrix= a1,1 a2,1 a3,1 a1,2 a2,2 a3,2 a1,3 a2,3 a3,3 n
相比较普通快速幂,矩阵快速幂只需要重新定义乘法的运算规则即可。这里提供一个用结构体来重定义运算符的方法:
矩阵快速幂的一个常见应用场景就是动态规划,也就是我们常说的矩阵加速动态规划算法。有关这方面的知识我会在后期单独出一篇文章来详细讲解。