算法8.数值的整数次方

题目描述

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

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

解题思路

方法一：快速幂解析

时间复杂度：$O(log_2n)$

空间复杂度：$O(1)$

代码如下

class Solution {
public:
    double myPow(double x, int n) {
        long long int positive_n = llabs(n);
        double res = 1.0;
        if(n==0)
            return res;
        while (positive_n != 0)
        {
            if(positive_n & 1){
                res *= x;
            }
            x *= x;
            positive_n >>= 1;
        }        
        if(n<0)
            res = 1/res;
        // cout<<res<<endl;
        return res;
    }
};

解法分析

由于题目说明不需要考虑大数运算，本题的关键就转到了时间复杂度上。用了常规方法试了多次$TLE$后，才知道普通的无脑for​循环是不可取的。联系到上一题求二进制1的个数，可以联想采用快速幂的方法来简化计算量。

将十进制数字 n 的二进制表示，可对快速幂进行数学化解释

主要步骤

• 循环32次，每次循环都执行$x=x^2$。将中间结果成倍增加，相比$for$减少了大量计算。
• 每次循环中执行n&1，如果为真则将结果res和x相乘，保存到res中。
• 每次循环结尾将n右移1位。

方法二：递归

时间复杂度：$O(log_2n)$

空间复杂度：$O(log_2n)$

代码如下

public double myPow(double x, int n) {
    if (n == 0)
        return 1;
    //如果n小于0，把它改为正数，并且把1/x提取出来一个
    if (n < 0)
        return 1 / x * myPow(1 / x, -n - 1);
    return (n % 2 == 0) ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
}

解法分析

总体思路和上述方法类似，只是换了种方法。