目录
  • 前言
  • 1. 暴力算法（fail）
  • 2. 优化取模运算（accept）
  • 3. 优化时间复杂度（accept）
  • 4. 优化 位运算（accept）

前言

此算法偶尔会出现在笔试以及面试中，特意花时间研究了下这题

题目：

求AB次方，并且保留最后几位数字（此题保留最后3位数）

例子：

21000,输出的结果保留3位数字

在笔试或者面试中看到此题，第一思路可能通过递归或者while遍历的想法，但细想一下，这么大的数字编程语言中任何一个变量或者计算机硬件机器也hold不住这么大的数字存储（越往后幂次越大，总是会溢出）

此时想到了海量数据如何存储：海量数据处理的高频面试题分析

那我就选择布隆过滤器：布隆过滤器的原理和实现详细分析（全）。（但可能会有误差）

硬件无法存储，那我就分片切片，甚至二进制移位来对应计算（但是我是21000次方，每一次的幂算，我都整这么复杂，这计算一个数字要花大半天？？）

冷静思考后，我发现想复杂了，应该从数学推导公式下手，才能提高算法的优化

以下章节对应算法复杂度的优化

1. 暴力算法（fail）

算法如下：

/* * base 为底数 * power 为指数 */ public long slowPower(long base,long power){ long result = 1; // 依次通过for循环，将其对应的数字乘 for(int i = 1 ;i <= power;i++){ result *= base; } // 保留最后的3位数字，求余1000 return result % 1000; }

或者使用while循环

public long slowPower(long base,long power){ long result = 1; while(power--){ result *= base; } return result % 1000; }

此处的代码执行的时候，就会出现数组越界

幂次运算，越到最后，爆炸式的增长：

对此求余是最好的想法（因为数值很大保留最后几位即可）

但数值本身就已经越界，而且爆炸增长也算不到最后的数值，更不用提及求余

2. 优化取模运算（accept）

从上面的理论可得知，在求到某一步的时候，数值已经越界，那可以提前求余在计算么

那就要从取模运算进行深入了解：取模运算百度百科

本身模运算与基本四则运算相似

  • (a + b) % p = (a % p + b % p) % p
  • (a - b) % p = (a % p - b % p ) % p
  • (a * b) % p = (a % p * b % p) % p
  • a ^ b % p = ((a % p)^b) % p

其他的重要的也可提前过一遍（哪天用得上）

结合律：

  • ((a+b) % p + c) % p = (a + (b+c) % p) % p
  • ((ab) % p * c)% p = (a * (bc) % p) % p

分配律：

  • (a+b) % p = ( a % p + b % p ) %p
  • ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p

特别是这个公式：(a * b) % p = (a % p * b % p) % p

算法如下：

/* * base 为底数 * power 为指数 */ public long fastPower(long base,long power){ long result = 1; // 依次通过for循环，将其对应的数字乘 for(int i = 1 ;i <= power;i++){ result *= base; result %= 1000; } // 保留最后的3位数字，求余1000 return result % 1000; }

3. 优化时间复杂度（accept）

上面的计算是21000，如果是2000000000000000000那时间复杂度随着指数的增加而增加，而且迭代的次数也特别多，那优化时间复杂度么？

通过幂次的巧妙处理，将其幂次计算的迭代减少

具体如下:（计算210）

pow(2,10)
= pow(4,5)
= pow(4,4) * pow(4,1)
= pow(16,2) * pow(4,1)
= pow(256,1) * pow(4,1)

  • 幂次为偶数，直接处理
  • 幂次为奇数，拆1 以及 偶数

知道所有的指数都变为1，将其相乘即为最终的结果

最终的算法：

/* * base 为底数 * power 为指数 */ public long fasterPower(long base,long power){ long result = 1; // 保证指数大于0 遍历 while (power > 0) { // 偶数 if (power % 2 == 0) { // 指数减半 power /= 2; // 底数平方，记得 （模的运算优化） base = base * base % 1000; } else { // 指数为奇数 // 拆分为1 和 偶数 power -= 1; // result乘底数 求余 并且放在result（提前存储） result = result * base % 1000; // power偶数，再操作一次 // 底数平方，记得 （模的运算优化） power /= 2; base = base * base % 1000; } } // 直接输出结果，已经不用求余了 return result; }

通过上面的算法发现冗余复杂了，提取公共部分合并

/* * base 为底数 * power 为指数 */ public long fasterPower(long base,long power){ long result = 1; // 保证指数大于0 遍历 while (power != 0) { // 奇数特殊判断 if (power % 2) { result = result * base % 1000; } // 再次操作一次，底数平方，记得 （模的运算优化） // 此处之所以不用减1，是因为 power 会向下取整 ，5 / 2 = 2 power /= 2; base = base * base % 1000; } // 直接输出结果，已经不用求余了 return result; }

4. 优化 位运算（accept）

除2（右移），可以使用移位来计算

// 非递归 public long fastestPower(long base,long power){ long result = 1; while (power != 0) { // 奇数特殊判断 if (power & 1) { result = result * base % 1000; } power >>= 1; base = base * base % 1000; } // 直接输出结果，已经不用求余了 return result; }

通过上面的层层递进进行优化，自然也可用递归

// 递归 public long fastestPower(long base,long power){ if(power == 0) { return 1; } return fastestPower(base * base, power >> 1) * (power & 1 == 1 ? base : 1); }

以上就是Java实现快速幂算法详解的详细内容，更多关于Java快速幂算法的资料请关注本网站其它相关文章！

您可能感兴趣的文章:

  • Java数据结构之快速幂的实现
  • Java语言实现快速幂取模算法详解