【C++】每日一题 50 Pow(x,n)

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

当需要计算x的n次幂时，可以使用递归或者迭代的方式来实现。

#include <iostream>double myPow(double x, int n) {if (n == 0) {return 1.0;} else if (n < 0) {return 1.0 / (x * myPow(x, -(n + 1)));} else {double half = myPow(x, n / 2);if (n % 2 == 0) {return half * half;} else {return x * half * half;}}
}int main() {double x = 2.0;int n = 10;std::cout << x << " raised to the power of " << n << " is: " << myPow(x, n) << std::endl;return 0;
}

在这个函数中，我们首先处理n为0和n为负数的情况，然后使用递归的方式计算x的n次幂。如果n为偶数，则将问题分解为计算x的n/2次幂，然后将结果相乘；如果n为奇数，则将问题分解为计算x的(n-1)/2次幂，然后将结果相乘，并额外乘以x。这样递归下去，直到n减小为0时返回1，从而完成了整数次幂的计算。

注意如果将这行代码

return 1.0 / (x * myPow(x, -(n + 1)));

替换为

 return 1.0/myPow(x,-n);

在
x =
1.00000
n =
-2147483648
时会溢出。
这个错误发生在对 -2147483648（即 INT_MIN）进行取反操作时。在 C++ 中，对 INT_MIN 进行取反会导致溢出，因为 INT_MIN 的绝对值大于 INT_MAX，无法表示为有符号整数的正值。
当 n 为 -2147483648 时，原始的代码中的 myPow(x, -n) 将会调用 myPow(x, 2147483648)，这个值超出了 int 类型的范围，导致了溢出错误。
为了解决这个问题，要不需要将 n 强制转换为长整型 long long 类型，以避免溢出。
要不通过(x * myPow(x, -(n + 1)))处理使其不溢出

时间复杂度分析：

当 n 为正数时，我们可以通过递归将指数减半，因此时间复杂度为 O(logn)，因为每次递归我们将指数减半。
当 n 为负数时，我们同样可以通过递归将指数加一减半，因此时间复杂度也为 O(logn)。

空间复杂度分析：

递归调用会使用栈空间，因此考虑递归的深度。由于每次递归将指数减半，所以递归的深度最多为 logn，因此空间复杂度为 O(logn)。
因此，经过修改后的 myPow 函数的时间复杂度为 O(logn)，空间复杂度也为 O(logn)。这意味着无论是时间开销还是空间开销，随着指数的增长，都是以对数级别的速度增加的。