leetcode Pow(x,n) 快速幂

 1 class Solution {
 2 public:
 3     double pow(double x, int n) {
 4         if(x == 1)
 5         {
 6             return 1;
 7         }
 8         if(x ==-1)
 9         {
10             if(n%2==0)
11             return 1;
12             else
13             return -1;
14         }
15         if (n < 0)
16     {
17         return 1 / pow(x, -n);
18     }
19         if (n == 0)
20         {
21         return 1;
22     }
23     if (n == 1)
24         return x;
25     else
26     {
27         if (n % 2 == 1)
28         {
29             double t = pow(x, n / 2);
30             return t * t * x;
31         }
32         else
33         {
34             double t = pow(x, n / 2);
35             return t*t;
36         }
37     }
38     }
39 };

这个东西叫做“快速幂”，相应的有矩阵快速幂，复数快速幂等，只要是运算或逻辑关系，满足结合律就能使用这个方法，O(lgn)在数据较大时的效果相当好的。