实现base的exponent次方,不考虑大数问题

实现base的exponent次方,不考虑大数问题

我们第一反应的是进行n次遍历。相乘得到结果

 func reduce(base:Double,exponent:Int)->Double{
   
  var result = base 
 return (1...expoent).forEach({result* = result})
 }

上面代码是我们最容易想到的代码但是会有很多问题。没有考虑传入0<x<1和x<1的情况

• 第一次改进

    double Power(double base,int exponent){

    if (base == 0) {
    return  0;
    }

    int absexponent = abs(exponent);

    double result = PowerWithUnsignedExponent(base,  absexponent);
  
    if (exponent<0) {

    result = 1/result;
    
    }  

     return  result
   
    }

加入了exponent 小于0和大于0小于1的判断。但是正常的值拿result的时候时间复杂度依然为O(n)

• 第二层改进。 我们总结规律可以发现，结果值满足。当expont为偶数的时候 result = a expont/2 * a expoent/2 .基数时为 (expoent-1)/2 * (exponent-1)/2 *base.所以我们只要计算出一半的数据，然后相乘即可。

double PowerWithUnsignedExponent(double base,int exponent){

if (exponent == 0) {
    return 1;
}
if (exponent == 1) {
    return base;
}
double result = PowerWithUnsignedExponent(base, exponent>>1);
result*= result;
//判断是否是奇数，如果是奇数则乘以base
if ((exponent & 0x1) == 1) {
    return result*=base;
}
return result;
}

这样时间复杂度为O(lgn).