实现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).
