leetcode Pow(x,n)高速べき乗
5082 ワード
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)はデータが大きい場合にかなり効果的である.