快速幂算法笔记

布满荆棘的人生 2022-08-29 13:48 182阅读 0赞

快速幂是一个logn时间复杂度的算法，其目的是计算an。在此基础上可以加入快速幂模，以便于存储数字。

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

方法1：最朴素的想法，`7*7=49`，`49*7=343`，… 一步一步算，共进行了9次乘法，也就是O(n)的复杂度。

这样算无疑太慢了。这时我们想到，也许可以拆分问题。

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

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

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

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

刚才是用的是一个二分的方法，所以我自然出现了一个递归方程  
![在这里插入图片描述][6057fcf4d7d66d4e798cd073ea8486e8.png_pic_center]

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

下面是代码：

1、递归版

//递归快速幂
    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;
        }
    }

2、非递归版

long long binpow(long long a, long long b) { 
      if (b == 0) return 1;
      long long res = binpow(a, b / 2);
      if (b % 2)
        return res * res * a;
      else
        return res * res;
    }

[6057fcf4d7d66d4e798cd073ea8486e8.png_pic_center]: /images/20220829/8c707f5eb962449593448d9430e04ae7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关 C#实现快速幂算法

C\实现快速幂算法快速幂算法是一种计算指数幂的高效算法，它通过将指数用二进制表示，进行位运算来减少计算次数。下面我们将介绍如何使用C\语言实现快速幂算法，并提供完整的源代码

刺骨的言语ヽ痛彻心扉/ 2024年03月23日 10:38/ 0 赞/ 66 阅读

相关【数论算法】快速幂

目录 1.概述 2.代码实现 > 本文参考 > LeetCode [50.Pow(x, n)][50.Pow_x_ n] 1.概述（1）快速幂

电玩女神/ 2023年10月07日 23:29/ 0 赞/ 35 阅读

相关算法 - 快速幂算法

参考博客 [https://blog.csdn.net/qq\_19782019/article/details/85621386][https_blog.csdn.ne

短命女/ 2023年07月04日 04:41/ 0 赞/ 37 阅读

相关算法笔记【5】快速幂

算法笔记【5】快速幂快速幂简介快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以Ologn的时间复杂度

古城微笑少年丶/ 2023年01月10日 14:41/ 0 赞/ 154 阅读

相关算法提高快速幂

快速幂讲解http://blog.csdn.net/xuruoxin/article/details/8578992 问题描述　　给定A, B, P，求(A^B) mod

深碍√TFBOYSˉ_/ 2022年09月27日 06:45/ 0 赞/ 154 阅读

相关快速幂算法笔记

快速幂是一个logn时间复杂度的算法，其目的是计算an。在此基础上可以加入快速幂模，以便于存储数字。让我们先来思考一个问题：7的10次方，怎样算比较快？方法1：最朴素的

布满荆棘的人生/ 2022年08月29日 13:48/ 0 赞/ 183 阅读

相关快速幂取模算法模板

在Miller Rabbin测试素数，就用到了快速幂取模的思想。这里总结下。求a^b%c（这就是著名的RSA公钥的加密方法），当a,b很大时，直接求解这个问题不太可能

分手后的思念是犯贱/ 2022年08月09日 13:46/ 0 赞/ 164 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 297 阅读

相关 [算法提高] 递归快速幂

理解递归的想法不难，关键是如何快速写出正确高效的递归。函数递归调用的基本形式： Type MyFunction(){ ...

逃离我推掉我的手/ 2022年03月06日 03:20/ 0 赞/ 190 阅读

相关快速求幂算法Java实现

文章目录快速求幂算法inJava 一、累乘二、化繁为简求幂快速求幂算法inJava 一、累乘最

╰半夏微凉°/ 2022年03月01日 06:38/ 0 赞/ 238 阅读