如何使用指数递归函数找到x^63的乘法次数以及如何证明它？
我将如何证明这个算法是 O(log n)？
public static long exponentiation(long x, int n){
if(n == 0){
return 1;
}
else if (n % 2 == 0){
x = exponentiation(x, n / 2);
return x * x;
}
else{
return x * exponentiation(x, n-1);
}
}
回答
对方法的每次递归调用exponentiation都是一个乘法步骤。因此，您需要计算递归调用的次数。有几种方法可以实现这一点。我选择向该方法添加另一个参数。
public static long exponentiation(long x, int n, int count) {
if (n == 0) {
System.out.println("steps = " + count);
return 1;
}
else if (n % 2 == 0) {
x = exponentiation(x, n / 2, count + 1);
return x * x;
}
else {
return x * exponentiation(x, n - 1, count + 1);
}
}
这是对方法的初始调用 exponentiation
exponentiation(2, 63, 0);
当我运行上面的代码时，打印出以下内容
public static long exponentiation(long x, int n, int count) {
if (n == 0) {
System.out.println("steps = " + count);
return 1;
}
else if (n % 2 == 0) {
x = exponentiation(x, n / 2, count + 1);
return x * x;
}
else {
return x * exponentiation(x, n - 1, count + 1);
}
}