Java實(shí)現(xiàn)快速冪算法詳解
前言
此算法偶爾會(huì)出現(xiàn)在筆試以及面試中，特意花時(shí)間研究了下這題
題目：
求AB次方，并且保留最后幾位數(shù)字（此題保留最后3位數(shù)）
例子：
21000,輸出的結(jié)果保留3位數(shù)字
在筆試或者面試中看到此題，第一思路可能通過(guò)遞歸或者while遍歷的想法，但細(xì)想一下，這么大的數(shù)字編程語(yǔ)言中任何一個(gè)變量或者計(jì)算機(jī)硬件機(jī)器也hold不住這么大的數(shù)字存儲(chǔ)（越往后冪次越大，總是會(huì)溢出）
此時(shí)想到了海量數(shù)據(jù)如何存儲(chǔ)：海量數(shù)據(jù)處理的高頻面試題分析
那我就選擇布隆過(guò)濾器：布隆過(guò)濾器的原理和實(shí)現(xiàn)詳細(xì)分析（全）。（但可能會(huì)有誤差）
硬件無(wú)法存儲(chǔ)，那我就分片切片，甚至二進(jìn)制移位來(lái)對(duì)應(yīng)計(jì)算（但是我是21000次方，每一次的冪算，我都整這么復(fù)雜，這計(jì)算一個(gè)數(shù)字要花大半天？？）
冷靜思考后，我發(fā)現(xiàn)想復(fù)雜了，應(yīng)該從數(shù)學(xué)推導(dǎo)公式下手，才能提高算法的優(yōu)化
以下章節(jié)對(duì)應(yīng)算法復(fù)雜度的優(yōu)化
1. 暴力算法（fail）
算法如下：
/*
* base 為底數(shù)
* power 為指數(shù)
*/
public long slowPower(long base,long power){
long result = 1;
// 依次通過(guò)for循環(huán)，將其對(duì)應(yīng)的數(shù)字乘
for(int i = 1 ;i <= power;i++){
result *= base;
}
// 保留最后的3位數(shù)字，求余1000
return result % 1000;
}
或者使用while循環(huán)
public long slowPower(long base,long power){
long result = 1;
while(power--){
result *= base;
}
return result % 1000;
}
此處的代碼執(zhí)行的時(shí)候，就會(huì)出現(xiàn)數(shù)組越界
冪次運(yùn)算，越到最后，爆炸式的增長(zhǎng)：
對(duì)此求余是最好的想法（因?yàn)閿?shù)值很大保留最后幾位即可）
但數(shù)值本身就已經(jīng)越界，而且爆炸增長(zhǎng)也算不到最后的數(shù)值，更不用提及求余
2. 優(yōu)化取模運(yùn)算（accept）
從上面的理論可得知，在求到某一步的時(shí)候，數(shù)值已經(jīng)越界，那可以提前求余在計(jì)算么
那就要從取模運(yùn)算進(jìn)行深入了解：取模運(yùn)算百度百科
本身模運(yùn)算與基本四則運(yùn)算相似
- (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
其他的重要的也可提前過(guò)一遍（哪天用得上）
結(jié)合律：
- ((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
特別是這個(gè)公式：(a * b) % p = (a % p * b % p) % p
算法如下：
/*
* base 為底數(shù)
* power 為指數(shù)
*/
public long fastPower(long base,long power){
long result = 1;
// 依次通過(guò)for循環(huán)，將其對(duì)應(yīng)的數(shù)字乘
for(int i = 1 ;i <= power;i++){
result *= base;
result %= 1000;
}
// 保留最后的3位數(shù)字，求余1000
return result % 1000;
}3. 優(yōu)化時(shí)間復(fù)雜度（accept）
上面的計(jì)算是21000，如果是210000000000000000000000000000那時(shí)間復(fù)雜度隨著指數(shù)的增加而增加，而且迭代的次數(shù)也特別多，那優(yōu)化時(shí)間復(fù)雜度么？
通過(guò)冪次的巧妙處理，將其冪次計(jì)算的迭代減少
具體如下:（計(jì)算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)
- 冪次為偶數(shù)，直接處理
- 冪次為奇數(shù)，拆1 以及 偶數(shù)
知道所有的指數(shù)都變?yōu)?，將其相乘即為最終的結(jié)果
最終的算法：
/*
* base 為底數(shù)
* power 為指數(shù)
*/
public long fasterPower(long base,long power){
long result = 1;
// 保證指數(shù)大于0 遍歷
while (power > 0) {
// 偶數(shù)
if (power % 2 == 0) {
// 指數(shù)減半
power /= 2;
// 底數(shù)平方，記得 （模的運(yùn)算優(yōu)化）
base = base * base % 1000;
} else {
// 指數(shù)為奇數(shù)
// 拆分為1 和 偶數(shù)
power -= 1;
// result乘底數(shù) 求余 并且放在result（提前存儲(chǔ)）
result = result * base % 1000;
// power偶數(shù)，再操作一次
// 底數(shù)平方，記得 （模的運(yùn)算優(yōu)化）
power /= 2;
base = base * base % 1000;
}
}
// 直接輸出結(jié)果，已經(jīng)不用求余了
return result;
}通過(guò)上面的算法發(fā)現(xiàn)冗余復(fù)雜了，提取公共部分合并
/*
* base 為底數(shù)
* power 為指數(shù)
*/
public long fasterPower(long base,long power){
long result = 1;
// 保證指數(shù)大于0 遍歷
while (power != 0) {
// 奇數(shù)特殊判斷
if (power % 2) {
result = result * base % 1000;
}
// 再次操作一次，底數(shù)平方，記得 （模的運(yùn)算優(yōu)化）
// 此處之所以不用減1，是因?yàn)?power 會(huì)向下取整 ，5 / 2 = 2
power /= 2;
base = base * base % 1000;
}
// 直接輸出結(jié)果，已經(jīng)不用求余了
return result;
}4. 優(yōu)化 位運(yùn)算（accept）
除2（右移），可以使用移位來(lái)計(jì)算
// 非遞歸
public long fastestPower(long base,long power){
long result = 1;
while (power != 0) {
// 奇數(shù)特殊判斷
if (power & 1) {
result = result * base % 1000;
}
power >>= 1;
base = base * base % 1000;
}
// 直接輸出結(jié)果，已經(jīng)不用求余了
return result;
}通過(guò)上面的層層遞進(jìn)進(jìn)行優(yōu)化，自然也可用遞歸
// 遞歸
public long fastestPower(long base,long power){
if(power == 0) {
return 1;
}
return fastestPower(base * base, power >> 1) * (power & 1 == 1 ? base : 1);
}以上就是Java實(shí)現(xiàn)快速冪算法詳解的詳細(xì)內(nèi)容，更多關(guān)于Java快速冪算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章給大家介紹java的concurrent用法，感興趣的朋友一起學(xué)習(xí)吧2015-10-10
這篇文章主要介紹了java獲取上一個(gè)月月份,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-09-09
使用Easyexcel實(shí)現(xiàn)不同場(chǎng)景的數(shù)據(jù)導(dǎo)出功能
這篇文章主要為大家詳細(xì)介紹了如何在不同場(chǎng)景下使用Easyexcel實(shí)現(xiàn)數(shù)據(jù)導(dǎo)出功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-03-03
Java語(yǔ)言中flush()函數(shù)作用及使用方法詳解
這篇文章主要介紹了Java語(yǔ)言中flush函數(shù)作用及使用方法詳解，具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01
Spring整合Quartz實(shí)現(xiàn)定時(shí)任務(wù)調(diào)度的方法
下面小編就為大家?guī)?lái)一篇Spring整合Quartz實(shí)現(xiàn)定時(shí)任務(wù)調(diào)度的方法。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-11-11
Jdk11使用HttpClient提交Http2請(qǐng)求的實(shí)現(xiàn)方法
這篇文章主要介紹了Jdk11使用HttpClient提交Http2請(qǐng)求的實(shí)現(xiàn)方法，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-08-08
Java方法重載和方法重寫(xiě)的區(qū)別到底在哪?
今天給大家?guī)?lái)的是關(guān)于Java的相關(guān)知識(shí),文章圍繞著Java方法重載和方法重寫(xiě)的區(qū)別到底在哪展開(kāi),文中有非常詳細(xì)的解釋,需要的朋友可以參考下2021-06-06
SpringBoot參數(shù)校驗(yàn)之@Validated的使用詳解
這篇文章主要通過(guò)示例為大家詳細(xì)介紹一下介紹了SpringBoot參數(shù)校驗(yàn)中@Validated的使用方法，文中的示例代碼講解詳細(xì)，需要的可以參考一下2022-06-06
提到RESTful?API大家勢(shì)必或多或少聽(tīng)說(shuō)過(guò),但是什么是RESTful?API?？如何理解RESTful?API?呢？今天咱們就來(lái)聊聊這個(gè)RESTful?API2023-11-11
Spring Boot使用線程池創(chuàng)建多線程的完整示例
在 Spring Boot 2 中,可以使用 @Autowired 注入 線程池（ThreadPoolTaskExecutor 或 ExecutorService）,從而管理線程的創(chuàng)建和執(zhí)行,以下是使用 @Autowired 方式注入線程池的完整示例,感興趣的朋友一起看看吧2025-03-03