x^n=x x x.....x
【分治法实现pow(x,n)函数的功能】朴素算法的时间复杂度是O(n)
采用分治（当n为偶数）
x^n=x^(n/2)*x^(n/2)
T(n)=2T(n/2)+O(1)
时间复杂度为O(logn)
我想的是采用函数的递归来实现
#includeint mypow(int x,int n)
{
int sum;
if(n==1) return x;
if(n&1)//n为奇数
{
sum=mypow(x,n/2)*mypow(x,n/2)*x;
}
else
{
sum=mypow(x,n/2)*mypow(x,n/2);
}
return sum;
}int main()
{
printf("%d\n",mypow(2,10));
}网上看到个大神这样来写
int my_pow(int x,int n)
{
if(n==0)
{
return 1;
}
int p=1;
while(n>0)
{
if(n&1)
{
p*=x;
}
x*=x;
n/=2;
}
return p;
}原理是一样的，但是没用递归，节省了很多开销~厉害啊
