求一个复杂度较优的乘方程序

Question

普通的做法(特殊情况等细节暂时忽略，主要考察复杂度（时间，空间）)就是：x的y次方
int z = 1;
for(int i=0;i<y;i++){
    z*=x;
}时间复杂度是O(y),求一个时间复杂度更小的，空间复杂度也要考虑。 谢谢

Answer 1

楼主可以看看这个，http://hi.baidu.com/jrckkyy/blog/item/9de487fa1ed7818e9f514662.html

Answer 2

public static double pow(double base, int exponent) {
    if (exponent < 0)
        return 1 / pow(base, -exponent);
    double power = 1;
    while(exponent > 0) {
        if((exponent & 1) == 1) {
            power *= base;
        }
        base *= base;
        exponent >>= 1;
    }
    return power;
}时间复杂度 O(lgN)

Answer 3

利用计算机知识计算 pow 的话，O(lgN) 算法复杂度已经是最小的了。如果利用数学知识和 IEEE 754 计算 pow 的话，可以将算法复杂度降到 O(1)，就像计算 Math.pow 用的本地数学函数库 fdlibm 计算 pow 那样。当然了，复杂度降到 O(1) 了，但是其内部使用的局部变量增多了。

Answer 4

java.lang.Math 的 pow 更为强大，其指数允许是 double 类型的。如果要计算指数为 double 类型冪的话，那用计算机算法就做不到了。

Answer 5

可以二分求方，或者根据二进制信息来求就更快了！
请看看：package naiti;import java.util.Scanner;public class PractiseB {
private static final int m = 9907; public static void main(String[] args) { // System.out.println((long)Math.pow(2, 31));
Scanner sc = new Scanner(System.in);
int testNum = sc.nextInt();
for (int i = 0; i < testNum; ++i) {
int a = sc.nextInt();
int b = sc.nextInt();
                        //求a^b
int x = 0;
long sum = 1;
for (x = bitLen(b); x > 0; --x) {
sum = (sum * sum) % m;
if (bitAt(b, x) > 0)
sum = (sum * a) % m;
}
System.out.println(sum);
}
} static int bitLen(int x) {
int d = 0;
while (x > 0) {
x >>= 1;
d++;
}
return d;
} static int bitAt(int x, int i) {
return (x & (1 << (i - 1)));
}
}