腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

Java實現(xiàn)快速冪算法詳解

更新時間：2022年10月14日 08:58:51 作者：碼農(nóng)研究僧

快速冪是用來解決求冪運算的高效方式。此算法偶爾會出現(xiàn)在筆試以及面試中，特意花時間研究了下這題，感興趣的小伙伴快跟隨小編一起學(xué)習(xí)一下

前言

此算法偶爾會出現(xiàn)在筆試以及面試中，特意花時間研究了下這題

題目：

求A^B次方，并且保留最后幾位數(shù)字（此題保留最后3位數(shù)）

例子：

2¹⁰⁰⁰,輸出的結(jié)果保留3位數(shù)字

在筆試或者面試中看到此題，第一思路可能通過遞歸或者while遍歷的想法，但細(xì)想一下，這么大的數(shù)字編程語言中任何一個變量或者計算機硬件機器也hold不住這么大的數(shù)字存儲（越往后冪次越大，總是會溢出）

此時想到了海量數(shù)據(jù)如何存儲：海量數(shù)據(jù)處理的高頻面試題分析

那我就選擇布隆過濾器：布隆過濾器的原理和實現(xiàn)詳細(xì)分析（全）。（但可能會有誤差）

硬件無法存儲，那我就分片切片，甚至二進制移位來對應(yīng)計算（但是我是21000次方，每一次的冪算，我都整這么復(fù)雜，這計算一個數(shù)字要花大半天？？）

冷靜思考后，我發(fā)現(xiàn)想復(fù)雜了，應(yīng)該從數(shù)學(xué)推導(dǎo)公式下手，才能提高算法的優(yōu)化

以下章節(jié)對應(yīng)算法復(fù)雜度的優(yōu)化

1. 暴力算法（fail）

算法如下：

/* 
* base 為底數(shù)
* power 為指數(shù)
*/
public long slowPower(long base,long power){
    long result = 1;
    
    // 依次通過for循環(huán)，將其對應(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í)行的時候，就會出現(xiàn)數(shù)組越界

冪次運算，越到最后，爆炸式的增長：

對此求余是最好的想法（因為數(shù)值很大保留最后幾位即可）

但數(shù)值本身就已經(jīng)越界，而且爆炸增長也算不到最后的數(shù)值，更不用提及求余

2. 優(yōu)化取模運算（accept）

從上面的理論可得知，在求到某一步的時候，數(shù)值已經(jīng)越界，那可以提前求余在計算么

那就要從取模運算進行深入了解：取模運算百度百科

本身模運算與基本四則運算相似

(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

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

結(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

特別是這個公式：(a * b) % p = (a % p * b % p) % p

算法如下：

/* 
* base 為底數(shù)
* power 為指數(shù)
*/
public long fastPower(long base,long power){
    long result = 1;
    
    // 依次通過for循環(huán)，將其對應(yīng)的數(shù)字乘
    for(int i = 1 ;i <= power;i++){
        result *= base;
        result %= 1000;
    }
    
    // 保留最后的3位數(shù)字，求余1000
    return result % 1000;
}

3. 優(yōu)化時間復(fù)雜度（accept）

上面的計算是2¹⁰⁰⁰，如果是2^{10000000000000000000000000000}那時間復(fù)雜度隨著指數(shù)的增加而增加，而且迭代的次數(shù)也特別多，那優(yōu)化時間復(fù)雜度么？

通過冪次的巧妙處理，將其冪次計算的迭代減少

具體如下:（計算2¹⁰）

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ōu)化）
            base = base * base % 1000;
            
        } else {
            // 指數(shù)為奇數(shù)
            // 拆分為1 和 偶數(shù)
            power -= 1;
            
            // result乘底數(shù) 求余 并且放在result（提前存儲）
            result = result * base % 1000;
            
            // power偶數(shù)，再操作一次
            // 底數(shù)平方，記得 （模的運算優(yōu)化）
            power /= 2;
            base = base * base % 1000;
        }
    }
    
    // 直接輸出結(jié)果，已經(jīng)不用求余了
    return result;
}

通過上面的算法發(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ōu)化）
        // 此處之所以不用減1，是因為 power 會向下取整 ，5 / 2 = 2 
        power /= 2;
        base = base * base % 1000;
     
    }
    
    // 直接輸出結(jié)果，已經(jīng)不用求余了
    return result;
}

4. 優(yōu)化位運算（accept）

除2（右移），可以使用移位來計算

// 非遞歸
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;
}

通過上面的層層遞進進行優(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實現(xiàn)快速冪算法詳解的詳細(xì)內(nèi)容，更多關(guān)于Java快速冪算法的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: