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)はデータが大きい場合にかなり効果的である.