Algorithm - Fast Power

Created by : Mr Dk.

2020 / 10 / 24 👨‍💻 16:11

Nanjing, Jiangsu, China

能够快速算底数的幂，时间复杂度由朴素算法的 O(n) 降低到 O(log(n))。

首先需要明确一个事实：计算机和人脑的运算方式不一样。人脑计算比较小的数字可以直接口算，而算大的数字比较慢；而计算机 CPU 中已经是设计好的电路，对于相同的运算符来说，不管操作数的大小，运算时间应当都是一致的。对于人脑来说，计算 7 * 7 的时间远快于 77777 * 77777；而对于 CPU 来说，时间基本上是一样的。因此，幂运算在计算机上的快慢，本质上取决于做乘法的次数，而不是 底数大小。

对于 7 ^ 10 来说，从人脑的思路出发，应当是不断计算 7 * 7^(n-1)，最终需要通过 9 次乘法完成。而在计算机上，基于分治的思路，很容易想到：如果先算 7^5 (假设通过人脑计算法需要 4 次乘法)，然后再多用一次乘法计算 7^5 * 7^5，最终岂不是只需要 5 次乘法 (姑且这么认为) 就能完成了？这里为什么能省乘法次数呢？因为 7^5 已经被计算过了，完全可以被重复使用。

同样，对于 7^5 来说，人脑算法需要 4 次乘法，而如果使用 7^2 * 7^2 * 7 的算法，只需要 (1 (7^2) + 2 (合并结果)) 共 3 次乘法即可。

以上就是 快速幂 算法的基础思想：

对于奇数次幂，x^y = x^(y/2) * x^(y/2) * x
对于偶数次幂，x^y = x^(y/2) * x^(y/2)

依次类推，递归的终点为 x^2 / x^1 / x^0。