声明：此文章用来记录我对于题目的解法及大佬们优秀的解答，部分代码是复制的别人的，所以此文章只是为了方便我日后重新看优秀的解答，如涉及代码版权请联系我删除。
1. 题目
问题
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例
输入：x = 2.00000, n = 10
输出：1024.00000
2. 解答
（1）我的暴力递归法
class Solution:# 递归方法def myPow(self, x: float, n: int) -> float:def f(x, n):if n < 0:n = -nif n == 0:return 1return x * f(x, n-1)if (n >= 0):return f(x, n)else:return 1/f(x, n)
这种方法很容易想到，但会报错RecursionError: maximum recursion depth exceeded in comparison，就是递归深度有限制。所以需要减少递归深度。下边就是我参考的别人的写法
（2）别人的递归法，时间复杂度O(logn)，空间复杂度O(logn)
class Solution:# 递归方法，大佬的做法def myPow(self, x: float, n: int) -> float:if n == 0:return 1elif n < 0:return 1/self.myPow(x, -n)elif n & 1:return x * self.myPow(x, n-1)else:return self.myPow(x*x, n//2)# else:# return x * self.myPow(x, n-1)
复杂度分析：递归几次就有多大的复杂度，最多递归次数是n为负数且n为奇数的时候，比n为正数且为偶数的情况多递归2次，常数级别的复杂度忽略不计；主要就看n为偶数的时候，这时最多递归次数为n的二进制位数，也就是lognlogn(底数为2)。时空复杂度差不多是这个水平
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/jian-zhi-offer-16-shu-zhi-de-zheng-shu-c-rgqy/
（3）快速幂方法
# 快速幂，时间复杂度O(log2n)，空间复杂度O(1)def myPow(self, x: float, n: int) -> float:if x == 0: return 0res = 1if n < 0: x, n = 1 / x, -nwhile n:if n & 1: res *= xx *= xn >>= 1return res
详细解析参考这位大佬的做法剑指offer 16