TypechoJoeTheme

Zt's Blog

搜索到 1 篇与 OI算法 的结果
2020-06-13

【OI算法】OI算法之快速幂

【OI算法】OI算法之快速幂
快速幂 顾名思义,快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。 问题引入:如何最快的算出 8^45 ?用最常规的方法,也就是 8×8×......×8×8 需要进行44次运算,显然是非常慢的,那么如何更快呢?我刚开始想到用二分法来算,这种方法的确可以减少一些运算次数,但显然还不够。我们需要的是:快速幂快速幂的核心思想是将指数转为二进制数,然后根据基础的数学知识进行化简,得到最终的结果。如刚才所说的 8^45 ,按照快速幂算法,将指数 45 转换为 101101 ,根据二进制的知识:45 = 2^5 * 1 +2^4 * 0 + 2^3 * 1 + 2^2 * 1 + 2^1 * 0 + 2^0 * 1 而数学基础知识告诉我们:a^(b+c) = a^b * a^c所以8^45 = 8^(2^5 * 1 +2^4 * 0 + 2^3 * 1 + 2^2 * 1 + 2^1 * 0 + 2^0 * 1) = 8^(2^5 * 1) * 8^(2^4 * 0) * 8^(2^3 * 1) * 8^(2^2 * 1)...
2020年06月13日
600 阅读
1 评论