leetcode 50. Pow(x, n)

 

目录

函数定义：

2. 处理特殊情况：

3. 处理负指数：

4. 处理偶数指数：

5. 处理奇数指数：

时间复杂度

空间复杂度

---

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0)
        {
            return 1;
        }
        if(n == 1) return x;
        if(n < 0)
        {
            if(n == -2147483648)
            {
                return 1 / (myPow(x,-(n+1))*x);
            }
            return 1 / myPow(x,-n);
        }
        if(n % 2 == 0)
        {
            double temp = myPow(x,n / 2);
            return temp * temp;
        }
        else
        {
            double temp = myPow(x,n / 2);
            return temp * temp * x;
        }
    }
};

1. 函数定义：

cpp复制代码

这定义了一个名为 myPow 的函数，它接受一个双精度浮点数 x 和一个整数 n 作为参数，并返回一个双精度浮点数。

2. 处理特殊情况：

cpp复制代码

如果 n 是0，任何数的0次方都是1，所以直接返回1。如果 n 是1，任何数的1次方就是其本身，所以直接返回 x。

3. 处理负指数：

cpp复制代码

如果 n 是负数，x^n 可以表示为 1 / (x^(-n))。但这里有一个特殊情况需要注意，即当 n 是 -2147483648 时（这是32位整数能表示的最小值）。在这种情况下，直接计算 -n 可能会导致整数溢出。因此，代码使用了 -(n+1) 来避免这个问题。

4. 处理偶数指数：

cpp复制代码

如果 n 是偶数，那么 x^n 可以写成 (x^(n/2))^2。这里通过递归调用 myPow(x, n/2) 来计算 x^(n/2)，然后将其平方。

5. 处理奇数指数：

cpp复制代码

如果 n 是奇数，那么 x^n 可以写成 x * (x^((n-1)/2))^2。同样地，这里通过递归调用 myPow(x, (n-1)/2) 来计算 x^((n-1)/2)，然后将其平方并乘以 x。

这个实现使用了递归和分解的方法，将大的指数分解为更小的部分，从而简化了计算。此外，它还特别处理了负指数和整数溢出的情况，确保了代码的健壮性。

时间复杂度

1. 基本情况：
   • 如果 n 是0或1，函数直接返回，时间复杂度为 O(1)。
   • 如果 n 是负数，并且等于 -2147483648，函数执行两次递归调用和一个乘法，时间复杂度为 O(log(|n|))。
2. 递归情况：
   • 对于偶数 n，函数执行一次递归调用和一次乘法，时间复杂度为 O(log(|n|))。
   • 对于奇数 n，函数执行一次递归调用和两次乘法，时间复杂度也是 O(log(|n|))。

综合所有情况，无论 n 的值是多少（正数、负数、大数、小数），myPow 函数的时间复杂度都是 O(log(|n|))。这是因为每次递归调用都将问题规模减半（对于偶数 n）或减小到接近一半（对于奇数 n），直到问题规模变为1。

空间复杂度

空间复杂度主要由递归调用栈的深度决定。在最坏的情况下（当 n 是负数且接近 -2147483648 时），递归深度可能接近 |n| 的绝对值。因此，空间复杂度在最坏情况下是 O(|n|)。然而，在平均情况下，空间复杂度仍然是 O(log(|n|))，因为递归树是平衡的。

总结：

• 时间复杂度：O(log(|n|))
• 空间复杂度：在最坏情况下是 O(|n|)，但在平均情况下是 O(log(|n|))。

这个实现是非常高效的，因为它利用了指数的性质来减少必要的计算量，并且递归调用栈的深度也相对较小。