一、题目
1、算法题目
“实现函数，计算x的n次幂。”
题目链接：
来源：力扣（LeetCode）
链接：50. Pow(x, n) - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1： 输入： x = 2.00000, n = 10 输出： 1024.00000 复制代码
示例 2： 输入： x = 2.10000, n = 3 输出： 9.26100 复制代码
二、解题
1、思路分析
这道题可以使用快速幂+递归的方法解题。
快速幂算法，本质就是分治算法，将大问题分解成小问题，然后递归解决。
快速幂算法：
比如要计算x8，可以按照x → x2 → x4 → x8的顺序，从x开始，每次将上一次的结果进行平方，3次后就可以得到x8的结果，而不需要对x乘8次x。
如果幂是偶数，比如x9，可以按照x → x2 → x4 → x9的顺序，这些步骤中，还是按照将上一次结果平方，而在x4 → x9的步骤中，需要将上一个结果进行平方，还需要额外乘一个x。
综上所述，可以推到出规律，如果要计算xn，首先判断n的奇偶：
- n为偶数，那么xn=yn
- n为奇数，那么xn=yn * x
接着就可以递归地得到结果了。
2、代码实现
代码参考：
public class Solution { //递归 public double MyPow(double x, int n) { return (n >= 0) ? res(x, n) : 1 / res(x, n); } private double res(double x, int n) { if(n == 0) return 1; double y = res(x, n / 2); return (n % 2 == 0) ? y * y :y * y * x; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(log n)
其中n为遍历的层数。
空间复杂度： O(log n)
其中n为遍历的层数。
三、总结
这道题还有更秀的一行解题法：
public class Solution { public double MyPow(double x, int n) { return Math.Pow(x,n); } } 复制代码
是不是秀的头皮发麻。。。
