剑指 Offer 16. 数值的整数次方

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

输入输出

1
2
3
4
5
6
7
8
9
输入：x = 2.00000, n = 10
输出：1024.00000

输入：x = 2.10000, n = 3
输出：9.26100

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

基本思路

  1. 快速幂与递归 时复O(logn)空复O(logn) 由递归层数决定

    • 分治算法 拆分成举例计算$x^{64}$ 则计算$x \rightarrow x^{2} \rightarrow x^{4} \rightarrow x^{8} \rightarrow x^{16} \rightarrow x^{32} \rightarrow x^{64}$ 从 x 开始，每次直接把上一次的结果进行平方，计算 66 次就可以得到 $x^{64}$ 的值 而不需要对x乘以63次x
    • 计算 $x^n$ 时我们可以先递归计算 $x^{n/2}$ 根据递归计算的结果 如果n为偶数那么 $x^n = y^2$ 如果n为奇数那么$x^n = y^2 \times x$
    • 递归的边界为n=0 任意数的0次方均为1

  2. 快速幂与迭代 时复O(logn)空复O(1)

    • 举例 $x^{11} = x^{2^{3}} \times x^{2^{1}} \times x^{2^{0}}$ 此时只运行了三次乘积 时间复杂度为O(logn)
    • (b & 1) == 1 判断最后一位是否为1 最终结果就是将每一位1所对应的权重相乘即可

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 快速幂+递归
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 N){
        if(N == 0) return 1.0;
        double y = quickpow(x, N/2);
        return N%2==0 ? y*y : y*y*x;
    }
}

// 快速幂+迭代
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0){
            x = 1/x;
            b = -b;
        }
        while(b > 0){
            if((b & 1) == 1){
                res *= x;
            }
            x *= x;
            b >>= 1;
        }
        return res;
    }
}