剑指 Offer 整数快速幂算法原理与实现 | 极客日志

编程语言java算法

剑指 Offer 整数快速幂算法原理与实现

快速幂算法用于高效计算乘方，时间复杂度为 O(logn)。文章讲解了取模运算公式及其证明，对比了递归与迭代（二进制位运算）两种实现方式，并结合 LeetCode 题目实现了处理正负指数的 pow 函数。

王初壹发布于 2024/12/250 浏览

剑指 Offer 整数快速幂算法原理与实现

前置知识

在之前的学习中，我们了解了二进制与位运算的操作。

取模运算是算法中的基础操作。为了避免溢出且减少冲突，通常使用一个足够大且为质数的数字进行取模，例如 10^9 + 7。

关于取模有一个重要公式：

(x * y) % z ==> ((x % z) * (y % z)) % z

证明： 假设 x = a * z + b, y = c * z + d，则：

(x * y) % z 
= ((a*z + b) * (c*z + d)) % z 
= (a*c*z*z + a*z*d + b*c*z + b*d) % z 
= 0 + 0 + 0 + (b*d) % z

b、d 为 x、y 本身的取模结果。

知道这个公式，当两个较大的数做乘法时，我们先求余再相乘，可以有效避免溢出。

快速幂算法

快速幂（Exponentiation by squaring）是一种简单而有效的算法，它可以 O(log n) 的时间复杂度计算乘方。

日常生活中，计算 3^10 可以通过内置函数或循环实现。若通过循环实现 x^y，时间复杂度为 O(n)。

对于大指数（如百万次方），需要优化。利用分治思想，将 x^y 转化为 (x*x)^(y/2)，时间复杂度降为 O(log n)。

若 y 不能被 2 整除，例如计算 3^10：

3^10 = (3*3)^5 = 9^5
9^5 = (9^4)*(9^1)

递归实现

def quick_pow(x, y):
    if y == 0:
        return 1
    ret = quick_pow(x, y // )
     ret * ret  y %  ==   ret * ret * x

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。在线工具，JavaScript 压缩与混淆在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

public int quickPow(int x, int y) {
    if (y == 0) {
        return 1;
    }
    int ret = quickPow(x, y / 2);
    return y % 2 == 0 ? ret * ret : ret * ret * x;
}

def quick_pow(x, y):
    res = 1
    while y:
        if y & 1:
            res *= x
        x *= x
        y = y >> 1
    return res

public int quickPow(int x, int y) {
    int ret = 1;
    while (y != 0) {
        if ((y & 1) != 0) {
            ret = ret * x;
        }
        x = x * x;
        y >>= 1;
    }
    return ret;
}

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quick_pow(N):
            if N == 0:
                return 1.0
            y = quick_pow(N // 2)
            return y * y if N % 2 == 0 else y * y * x
        return quick_pow(n) if n >= 0 else 1.0 / quick_pow(-n)

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickPow(x, N) : 1.0 / quickPow(x, -N);
    }
    public double quickPow(double x, long y) {
        if (y == 0) {
            return 1.0;
        }
        double ret = quickPow(x, y / 2);
        return y % 2 == 0 ? ret * ret : ret * ret * x;
    }
}

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(x, N):
            ans = 1.0
            while N > 0:
                if N % 2 == 1:
                    ans *= x
                x *= x
                N //= 2
            return ans
        return quickMul(x, n) if n >= 0 else 1.0 / quickMul(x, -n)

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickPow(x, N) : 1.0 / quickPow(x, -N);
    }
    public double quickPow(double x, long y) {
        double ret = 1.0;
        while (y != 0) {
            if ((y & 1) != 0) {
                ret = ret * x;
            }
            x = x * x;
            y >>= 1;
        }
        return ret;
    }
}