数值的整次方.md

数值的整次方

题目描述

时间限制：1秒

空间限制：32768K

给定一个double类型的浮点数base和int类型的整数exponent。

求base的exponent次方。

解题思路

暴力解法，四重if

public double Power(double base, int exponent) {
    if (exponent == 0) {
        return 1;
    } else if (exponent == 1) {
        return base;
    } else if (exponent < 0) {
        int newExponent = -(exponent);
        return 1 / (base * Power(base, newExponent - 1));
    } else {
        return base * Power(base, exponent - 1);
    }
}

优化

因为 (x*x)n/2 可以通过递归求解，并且每次递归 n 都减小一半，因此整个算法的时间复杂度为 O(logN)。 $$ x^{n} = \begin{cases} (x * x)^{n/2} & n%2 = 0 \ x * (x * x)^{n/2} & n%2 = 1\ \end{cases} $$

public double Power(double base, int exponent) {
    if (exponent == 0) {
        return 1;
    }
    if (exponent == 1) {
        return  base;
    }
    // 设置一个变量，记录exponent次数是否为负
    boolean isNegative = false;
    if (exponent < 0) {
        exponent = - exponent;
        isNegative = true;
    }
    // 求模递归
    double power = Power(base * base, exponent / 2);
    if (exponent % 2 != 0) {
        power = base * power;
    }
    return isNegative ? 1 / power : power;
}