难度: Medium
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1-104 <= xn <= 104注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/
运行时间: 36 ms
内存: 14.9 MB
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
return 1 / x * self.myPow(1 / x, -n - 1)
if n % 2 == 0:
return self.myPow(x * x, n // 2)
else:
return x * self.myPow(x * x, n // 2)
此题解采用了递归方式实现快速幂算法。快速幂算法通过将幂分解为多个较小的幂，以减少乘法操作的次数。1. 如果幂n为0，返回1。2. 如果幂n为负数，计算x的-n次幂并取倒数。3. 如果幂n为偶数，将问题分解为求(x*x)的n/2次幂。4. 如果幂n为奇数，将问题分解为求x乘以(x*x)的(n//2)次幂。
时间复杂度: O(log n)
空间复杂度: O(log n)
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1 # n为0时，任何数的0次幂都为1
if n < 0:
return 1 / x * self.myPow(1 / x, -n - 1) # 处理n为负的情况，利用x的-n次幂等于1/x的n次幂
if n % 2 == 0:
return self.myPow(x * x, n // 2) # n为偶数时，x^n = (x*x)^(n/2)
else:
return x * self.myPow(x * x, n // 2) # n为奇数时，x^n = x*(x*x)^(n//2)
在处理幂n为负数时，使用`1 / x * self.myPow(1 / x, -n - 1)`的原因在于减少递归深度和计算复杂性。如果直接使用`self.myPow(x, -n)`，则在递归内部会首先计算x的-n次幂，这会导致在递归调用中对x的值进行多次倒数转换，增加计算量和误差。而`1 / x * self.myPow(1 / x, -n - 1)`方法通过先计算1/x，再递归计算剩余的(-n-1)次幂，有效地利用了已有的递归结构，同时避免了额外的倒数操作，使得递归过程更加高效和稳定。
确保浮点数计算精度主要依靠编程语言本身的浮点数处理机制。大多数现代编程语言使用IEEE标准的浮点数表示法，这种表示法能在一定范围内提供精确的结果。在算法实现中，可以通过限制递归深度、优化算法结构等方式减少累积误差。此外，特别是在x很小或n很大的情况下，可以考虑使用更高精度的数据类型（如Python中的`decimal`模块），或者实施算法优化措施，如使用尾递归优化等，以降低误差传递和堆栈溢出的风险。
将n为奇数的情况处理为`x * self.myPow(x * x, n // 2)`的优势在于，这样的分解可以有效地减少递归调用的次数。当n为奇数时，直接使用`x * self.myPow(x * x, n // 2)`可以将乘法运算次数减半，因为每次递归都是对n进行整除2的操作。这种方法不仅优化了乘法操作的次数，还通过每次递归减少n的值，加快了递归的收敛速度，从而提高了整体的计算效率。