[人工智能]50. Pow(x n)

根据 n 的取值对函数计算的影响， 得出结论①如下：

$$Pow(x,n)=\{\begin{array}{l}{x}^n,(n>=0)\\ (1/x^n),(n<0)\end{array}$$

而根据幂运算法则“同底数幂的乘法：底数不变，指数相加幂的乘方”，有

$$x^m?x^n=x^{m+n}$$

假设 $$f(n)=Pow(x,n)$$

于是有结论②如下：

$$f(n)=\{\begin{array}{l}f(n/2)?f(n/2),(n是偶数)\\ f(n/2)?f(n/2)?x,(n是奇数)\end{array}$$

可以看出，当 x 确定时，f(n)可以转化为一个与原问题相似的但规模较小（n/2）的问题来求解，所以使用递归完全可以解决该问题，代码如下：

public static double myPow(double x, int n) {
    // 因为 n 需要转成正数来处理，所以使用 long 避免越界
    long m = n;
    // 结论①
    return m >= 0 ? quickMul(x, m) : 1.0 / quickMul(x, -m);
}

public static double quickMul(double x, long n) {
    if (n == 0) return 1.0;
    double half = quickMul(x, n / 2);
    // 结论②
    return n % 2 == 0 ? half * half : half * half * x;
}

复杂度分析:

时间复杂度：O(㏒n)，即为递归的层数。

空间复杂度：O(㏒n)，即为递归的层数。这是由于递归的函数调用会使用栈空间。