LeetCode题解：数的N次方

题目描述

实现Pow(x，n)，即计算x的n次幂函数（即，x^n）。

示例

• 示例1
  输入：x = 2.00000, n = 10
  输出：1024.00000
• 示例2
  输入：x = 2.10000, n = 3
  输出：9.26100
• 示例3
  输入：x = 2.00000, n = -2
  输出：0.25000

方法思路

快速幂+递归
举个例子：我们要计算x^64，我们可以按照：

image.png
的顺序计算6次，就可以得到最终的结果。
再举一个例子：如果我们要计算x^77，我们可以按照：
image.png
的顺序，在最后一步之前我们得到x^76，只需要再将结果乘一个x就可以得到最终的结果。

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N>0?quickMul(x,N) : 1.0/quickMul(x,-N);
    }
    public double quickMul(double x,long N){
        if(N==0){
            return 1.0;
        }
        ，double y = quickMul(x,N/2);
        return N%2==0? y*y : y*y*x;
    }
    
}

复杂度分析

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