LeetCode 50. Pow(x, n)

题目要求很简单，要求实现幂函数，但是如果考虑的太简单那就太天真了，比如像这样写：

 1 class Solution {
 2 public:
 3     double myPow(double x, int n) {11         double res = 1;
12        for (int i = 0; i < n; i++)
13            res *= x;
14         return res;
15     }
16 };

这样就没有考虑n为负数或者n为0的情况，即使考虑上，添加进去，也会发现超时，线性复杂度对这道题来说确实太高了。

不妨这样考虑，利用递归把n折半，一直到最后n为1 的简单情况，代码如下：

 1 class Solution {
 2 public:
 3     double myPow(double x, int n) {
 4         if (n < 0)
 5         {
 6             x = 1 / x;
 7             n = -n;
 8         }
 9         return power(x, n);
10     }
11     double power(double x, int n)
12     {
13         double res = 1.0;
14         if (n == 0)
15             return 1.0;
16         double half = power(x, n / 2);
17         if (n % 2)
18             return half * half * x;
19         else
20         return half * half;
21     }
22     
23     
24 };

时间复杂度：O(logn)

空间复杂度：O(logn)

当然还可以用迭代的方法，从小到大计算，避免了递归中重复的压栈与弹出，可以降低空间复杂度，但是要注意n的奇数偶数情况

 1 class Solution {
 2 public:
 3     double myPow(double x, int n) {
 4         double res = 1.0;
 5         for (int i = n; i; i /= 2)
 6         {
 7             if (i % 2)
 8                 res *= x;
 9             x *= x;
10         }
11         return n < 0 ? 1 / res : res;
12     }
13     
14 };

时间复杂度：O(logn)

空间复杂度：O(1)