亲宝软件园·资讯

展开

Java快速幂算法

码农研究僧 人气:0

前言

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

题目:

求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

算法如下:

/* 
* 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,如果是210000000000000000000000000000那时间复杂度随着指数的增加而增加,而且迭代的次数也特别多,那优化时间复杂度么?

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

具体如下:(计算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,将其相乘即为最终的结果

最终的算法:

/* 
* 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);
}

加载全部内容

相关教程
猜你喜欢
用户评论