【数论算法】快速幂

电玩女神 2023-10-07 23:29 55阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现

> 本文参考  
> LeetCode [50.Pow(x, n)][50.Pow_x_ n]

## 1.概述 ##

（1）快速幂 (Fast Power)，顾名思义，就是快速算底数 x 的 n 次幂。其核心思想就是每一步都**把指数减半**，而相应的底数做**平方运算**。这样不仅能把非常大的指数给快速变小，所需要执行的循环次数也变小，而最后表示的结果不会变化。

（2）快速幂算法的本质是**分治算法**。例如我们要计算  x 64 x^\{64\} x64 ，我们可以按照：

x x x →  x 2 x^2 x2 →  x 4 x^4 x4 →  x 8 x^8 x8 →  x 16 x^\{16\} x16 →  x 32 x^\{32\} x32 →  x 64 x^\{64\} x64

的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到  x 64 x^\{64\} x64 的值，而不需要对 x 乘 63 次 x。而如果我们要计算  x 77 x^\{77\} x77，我们可以按照：

x x x →  x 2 x^2 x2 →  x 4 x^4 x4 →  x 9 x^9 x9 →  x 19 x^\{19\} x19 →  x 38 x^\{38\} x38 →  x 77 x^\{77\} x77

的顺序，在  x x x →  x 2 x^2 x2、 x 2 x^2 x2 →  x 4 x^4 x4、 x 19 x^\{19\} x19 →  x 38 x^\{38\} x38 这些步骤中，我们直接把上一次的结果进行平方；而在  x 4 x^4 x4 →  x 9 x^9 x9、 x 9 x^9 x9 →  x 19 x^\{19\} x19、 x 38 x^\{38\} x38 →  x 77 x^\{77\} x77 这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。

（3）直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，**分治的思想**就十分明显了：

*  当我们要计算  x n x^n xn 时，我们可以先递归地计算出  y = x ⌊ n / 2 ⌋ y = x^\{\\lfloor n/2 \\rfloor\} y=x⌊n/2⌋ ，其中  ⌊ a ⌋ \\lfloor a \\rfloor ⌊a⌋ 表示对 a 进行下取整；
 *  根据递归计算的结果，如果 n 为偶数，那么  x n x^n xn =  y 2 y^2 y2；如果 n 为奇数，那么  x n x^n xn =  y 2 y^2 y2 \*  x x x；
 *  递归的边界为 n = 0，任意数的 0 次方均为 1。

（4）由于每次递归都会使得指数减少一半，因此递归的层数为 log2n，，故**其时间复杂度为 O(log2n)，与朴素的 O(n) 方法（即 n 个底数直接相乘）相比效率有了极大的提高**。

## 2.代码实现 ##

（1）快速幂的**递归**代码如下，其时间复杂度为 O(log2n)。

class Solution {
        
    
        //求 x 的 n 次幂
        public double myPow(double x, int n) {
        
            long N = n;
            if (N >= 0) {
        
                return quickMul(x, N);
            } else {
        
                return 1.0 / quickMul(x, N);
            }
        }
        
        private double quickMul(double x, long N) {
        
            if (N == 0) {
        
                return 1.0;
            }
            double y = quickMul(x, N / 2);
            if (N % 2 == 0) {
        
                return y * y;
            } else {
        
                return y * y * x;
            }
        }
    }

（2）快速幂的**非递归**代码如下，其时间复杂度为 O(log2n)。

class Solution {
        
        
        //求 x 的 n 次幂
        public double myPow(double x, int n) {
        
            long N = n;
            if (N >= 0) {
        
                return quickMul(x, N);
            } else {
        
                return 1.0 / quickMul(x, -N);
            }
        }
        
        private double quickMul(double x, long N) {
        
            double res = 1.0;
            //贡献的初始值为 x
            double x_contribute = x;
            //在对 N 进行二进制拆分的同时计算答案
            while (N > 0) {
        
                if (N % 2 == 1) {
        
                    // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    res *= x_contribute;
                }
                //将贡献不断地平方
                x_contribute *= x_contribute;
                //舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                N /= 2;
            }
            return res;
        }
    }

[50.Pow_x_ n]: https://leetcode.cn/problems/powx-n/solution/powx-n-by-leetcode-solution/