算法笔记【5】快速幂

古城微笑少年丶 2023-01-10 14:41 172阅读 0赞

# 算法笔记【5】 快速幂 #

## 快速幂简介 ##

**快速幂**（**Exponentiation by squaring**，平方求幂）是一种简单而有效的小算法，它可以以Ologn的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

让我们先来思考一个问题：**7的10次方，怎样算比较快？**

**方法1：最朴素的想法，`7*7=49`，`49*7=343`，… 一步一步算，共进行了9次**乘法。

这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。

**方法2：先算7的5次方，即`7*7*7*7*7`，再算它的平方，共进行了5次**乘法。

但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。

**方法3：先算`7*7`得49，则7的5次方为`49*49*7`，再算它的平方，共进行了4次**乘法。

模仿这样的过程，我们得到一个在 Ologn 时间内计算出幂的算法，也就是快速幂。

## 递归快速幂 ##

刚刚我们用到的，无非是一个**二分**的思路。我们很自然地可以得到一个递归方程：

![在这里插入图片描述][20210124235535292.png_pic_center]

计算a的n次方，如果n是偶数（不为0），那么就**先计算a的n/2次方，然后平方**；如果n是奇数，那么就**先计算a的n-1次方，再乘上a**；递归出口是**a的0次方为1**。

递归快速幂的思路非常自然，代码也很简单（直接把递归方程翻译成代码即可）：

public static int qpow(int a, int n) { 
        if (n == 0) { 
            return 1;
        } else if (n % 2 == 1) { 
            return qpow(a, n - 1) * a;
        } else { 
            int temp = qpow(a, n / 2);
            return temp * temp;
        }
    }

注意，这个temp变量是必要的，因为如果不把a^(n/2)记录下来，直接写成qpow(a, n /2)，那会计算两次a^(n/2)，整个算法就退化为了 O(N) 。

大家知道，递归虽然**简洁**，但会产生**额外的空间开销**。我们可以把递归改写为循环，来避免对栈空间的大量占用，也就是**非递归快速幂**。

## 非递归快速幂 ##

我们换一个角度来引入非递归的快速幂。还是7的10次方，但这次，我们把10写成**二进制**的形式，也就是 （1010）。

现在我们要计算7^(1010) ，可以怎么做？我们很自然地想到可以把它拆分为7(1000)\*7(10)实际上，对于任意的整数，我们都可以把它拆成若干个 7(100…)的形式相乘。而这些7(100…)，恰好就是71，72，7^4……我们只需**不断把底数平方**就可以算出它们。

我们先看代码，再来仔细推敲这个过程：

public static int qpow2(int a, int n) { 
            int ans = 1;
    
            for (int i = n; i > 0; i >>= 1) { 
                if (i % 2 == 1) { 
                    ans *= a;
                }
                a *= a;
            }
    
            return ans;
        }

最初ans为1，然后我们一位一位算：

1010的最后一位是0，所以a1这一位不要。然后1010变为101，a变为a2。

101的最后一位是1，所以a^2这一位是需要的，乘入ans。101变为10，a再自乘。

10的最后一位是0，跳过，右移，自乘。

然后1的最后一位是1，ans再乘上a^8。循环结束，返回结果。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]

这里的位运算符，>>是右移，表示把二进制数往右移一位，相当于/2；&是按位与，&1可以理解为取出二进制数的最后一位，相当于%2==1。这么一等价，是不是看出了递归和非递归的快速幂的关系了？虽然非递归快速幂因为牵扯到二进制理解起来稍微复杂一点，但基本思路其实和递归快速幂没有太大的出入。

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[20210124235535292.png_pic_center]: /images/20221119/e3aae9dfe780452b8f137b080317e7de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/a960055bc5fa4b77b7d03aa91513ee73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200721144257696.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70