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實(shí)現(xiàn)單例的五種方式,小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-07-07
Jmeter多種定時(shí)器實(shí)現(xiàn)方法解析
這篇文章主要介紹了Jmeter多種定時(shí)器實(shí)現(xiàn)方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09
mybatis批量插入,批量更新以及null值問(wèn)題的解決
這篇文章主要介紹了mybatis批量插入,批量更新以及null值問(wèn)題的解決,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01
JFrame中添加和設(shè)置JPanel的方法實(shí)例解析
這篇文章主要介紹了JFrame中添加和設(shè)置JPanel的方法實(shí)例解析，具有一定借鑒價(jià)值2018-01-01
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
抽象工廠模式用于產(chǎn)品族的構(gòu)建。抽象工廠是所有形態(tài)的工廠模式中最為抽象和最具一般性的一種形態(tài)。抽象工廠是指當(dāng)有多個(gè)抽象角色時(shí)使用的一種工廠模式。抽象工廠模式可以向客戶端提供一個(gè)接口，使客戶端在不必指定產(chǎn)品的具體情況下，創(chuàng)建多個(gè)產(chǎn)品族中的產(chǎn)品對(duì)象2021-06-06
Java8?CompletableFuture?runAsync學(xué)習(xí)總結(jié)submit()?execute()等
這篇文章主要介紹了Java8?CompletableFuture?runAsync學(xué)習(xí)總結(jié)submit()?execute()等，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-10-10
這篇文章主要為大家詳細(xì)介紹了java中密文的創(chuàng)建和校驗(yàn)的相關(guān)知識(shí),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-04-04
詳解Java如何在業(yè)務(wù)代碼中優(yōu)雅的使用策略模式
這篇文章主要為大家介紹了Java如何在業(yè)務(wù)代碼中優(yōu)雅的使用策略模式,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價(jià)值,感興趣的可以了解下2023-08-08
使用 Resttemplate 調(diào)用 DMS 文件服務(wù)器 Http 接口,出現(xiàn) 500 異常報(bào)錯(cuò),所以本文給大家介紹了Resttemplate上傳文件500異常的原因及解決方法,需要的朋友可以參考下2024-08-08