leetcode|LeetCode Pow(x,n)（分治法） leetcode|leetcode

大家好，我是刘天昊，今天来说说这题吧，之前有写过这题，那么先看题目
Implement pow(x, n).

实现x的n次方的计算
那么先来个正常人的思路，x*x*x......*x也就是n个x相乘，so，O（n），naive
挺好线性的实现了这个，你会发现
你提交不上去，这个时候就要思考了
啊
我们要找个比O（n）还要小的时间复杂度
ok先不考虑n的奇数和偶数问题
x的n次方==x的n／2次方 * x的n／2次方
如果我们这样递归下去一直到n==1或者n==0的时候终止
我们会发现算法的时间复杂度降到了O（lgn）（怎么计算，算法导论上的主定理可以去计算）这种低轨的通式
我先写出来
T（n）=T（n／2）+O（1）（这里我们实际用的是不是大O渐进法，算法导论上会有，奈何那个符号我打不出来，懒的百度了）
再这里提下当n为奇数的时候x的n次方==x的n-1／2次方 * x的n-1/2次方 *x；
好废话太多这次惯例
po上代码

double Calulate(double x,int n) { double res; if(x==0) { return 0; } if(n==0) { return 1; } if(n==1) { return x; } if(n%2==0) { res=Calulate(x,n/2)*Calulate(x,n/2); } else if(n%2==1) { res=Calulate(x,(n-1)/2)*Calulate(x,(n-1)/2)*x; } return res; } double myPow(double x, int n) { double res; if(x==1) { return 1; } if(x==-1) { if(n%2==0) { return 1; } if(n%2==1) { return -1; } } if(x==0) { return 0; } if(n>0) { res=Calulate(x,n); return res; } else if(n<0) { n=-n; x=1/x; res=Calulate(x,n); return res; } return 1; }

【leetcode|LeetCode Pow(x,n)（分治法）】那么各位看官可以看看怎么去简化代码
这次就到这里
————————————————————————————————————————————————————————————————
回头看了看自己的代码以前写的有些糟糕重新po两份高质量的自己写的代码
这是快速幂的
class Solution {
public:
double myPow(double x, int n) {
long long num = n ;
bool flag = false ;
if( n < 0 ){
flag = true ;
num =- num ;
}
double res =1 ;
while( num ){
if( num&1 ) res = res*x ;
x = x*x ;
num>>=1;
}
if( flag )
res = 1/res ;
return res ;
}
};

这是分治的
class Solution {
public:
double myPow(double x, int n) {
if( n < 0 )
x= 1/x;
return d_c( x , n ) ;
}
double d_c( double x , int n){
if( n == 0 )
return 1 ;
if( n == 1 )
return x ;
double res = d_c( x , n/2 );
if( n &1 )
return res*res*x;
else
return res*res;
}
};