剑指 Offer 16. 数值的整数次方 -- 快速幂

0 题目描述

leetcode原题：剑指 Offer 16. 数值的整数次方

1 快速幂解法

快速幂实际上是二分思想的一种应用。
二分推导： x n = x n / 2 × x n / 2 = ( x 2 ) n / 2 , x^{n}=x^{n / 2} \times x^{n / 2}=\left(x^{2}\right)^{n / 2}, xn=xn/2×xn/2=(x2)n/2, 令 n / 2 n / 2 n/2 为整数, 则需要分为奇偶两种情况（设向下取整除 法符号为 " / / " / / " //" ) :
∘ \circ ∘ 当 n n n 为偶数： x n = ( x 2 ) n / / 2 x^{n}=\left(x^{2}\right)^{n / / 2} xn=(x2)n//2;
∘ \circ ∘ 当 n n n 为奇数： x n = x ( x 2 ) n / / 2 , x^{n}=x\left(x^{2}\right)^{n / / 2}, xn=x(x2)n//2, 即会多出一项 x x x;

算法流程：

1. 当 x = 0 x=0 x=0 时：直接返回 0 (避免后续 x = 1 / x x=1 / x x=1/x 操作报错 ) ) ) 。
2. 初始化 r e s = 1 \mathrm{res}=1 res=1;
3. 当 n < 0 n<0 n<0 时：把问题转化至 n ≥ 0 n \geq 0 n≥0 的范围内，即执行 x = 1 / x , n = − n x=1 / x, n=-n x=1/x,n=−n;
4. 循环计算：当 n = 0 n=0 n=0 时跳出
   1. 当 n & 1 = 1 n \& 1=1 n&1=1 时：将当前 x x x 乘入 r e s ( r e s \quad( res( 即 r e s ∗ = x ) r e s *=x) res∗=x);
   2. 执行 x = x 2 ( x=x^{2} \quad( x=x2( 即 x ∗ = x ) x *=x) x∗=x);
   3. 执行 n n n 右移一位 (即 n > > = 1 n>>=1 n>>=1 ) 。
5. 返回 r e s r e s res 。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: return 0
        res = 1
        if n < 0: 
            x, n = 1 / x, -n
        while n:
            if n & 0x1: res *= x
            x *= x
            n >>= 1
        return res

递归解法：
（注意：0的0次方在数学上没有意义，而且0没有倒数）

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: return 0
        if n >= 0: 
            return self.power(x, n)
        return self.power(1/x, -n)
        
    def power(self, x: float, n: int):
        if n == 0: return 1
        r = self.power(x, n // 2)
        if n & 1:
            return r*r*x
        return r*r

复杂度分析：
时间复杂度: O ( log ⁡ 2 N ) O(\log _2 N) O(log2​N) ，二分的时间复杂度为对数级别。
空间复杂度: O ( N ) O(N) O(N)，递归写法有一个栈空间。

参考资料

面试题16. 数值的整数次方（快速幂，清晰图解）