java - 如何使用指数递归函数找到 x^63 的乘法次数以及如何证明它？

Question

我将如何证明这个算法是 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);
    }
}

Answer 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);

当我运行上面的代码时，打印出以下内容

steps = 11