1、先来个例题:
取值范围:
- -100.0 < x < 100.0
- -231 <= n <= 231-1
举个例子:
输入:x=2 n=10
输出:1024
输入:x=2 n=-2
输出:0.25 (因为1/4=0.25)
给出方法
public double myPow(double x, int n) {
}
2、分析
思路一:
蛮力法
根据幂函数定义直接求解,即2的10次方=2 * 2 *… * 2(10个2相乘)
代码实现:略
优点:思路清晰,简单直接易懂。
缺点:时间复杂度O(n),当n足够大时,程序运行超时。
按照目前思路,没有太多优化提升的余地。
思路二:
减治法-二分查找
减治法的基本思路是,将当前实例的解与其较小实例解建立关系。
先看个例子:
当n>0时,
1)n是偶数,求解等价于(n/2)^2,比如上面的10/2=5。
2)当n是奇数,等价于x * x^(n-1),
比如
当n<0时,
基本类似n>=0的情况。
当n=0时,直接返回1。
代码实现:
第一版
public double myPow(double x, int n) {
while(n>=1 || n<=-1){
if(n % 2==0){
n=n/2;
if(n>0){
return myPow(x,n)*myPow(x,n);
}else {
n=-n;
return 1/myPow(x,n)*myPow(x,n);
}
}else {
if(n==1) return x;
if(n==-1) return 1/x;
if(n>0){
n--;
return x*myPow(x,n);
}else {
n++;
n=-n;
return 1/(x*myPow(x,n));
}
}
}
return 1;
}
运行后仍然超时,稍微修改一下。
第二版
将下面这行代码
return myPow(x,n)*myPow(x,n);
修改为:
double y=myPow(x,n);
return y*y;
Tips:
递归时,可使用变量,尽量减少递归的次数。否则容易出现栈溢出或超时等问题。
运行通过,缺点也很明显。代码有点冗长,分了三大种情况,可以继续抽象。
第三版
public double quickMul(double x, long N) {
if (N == 0) {
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
与之前的版本相比:
a. 更加充分的利用了递归的特性,不再需使用while。
b. 使用三目表达式
减少了冗余繁琐的if…else…
同样的,也增加的理解的难度。
c.更加抽象
结束递归的口径唯一,进行了更多的抽象。代码更加简洁。
3、小结
二分查找是减治法的一个具体实现算法,他将求解n与n/2联系起来,找到之间关联。然后利用这种关联,加上结束条件(比如n=1或者n=0时,有已知值)。
旨在降低时间复杂度,提高运行效率。相应的,代码可能不太好理解。