如何用指数递归函数求x^63的乘法数，以及如何对其进行对齐？

Question

我将如何证明这个算法是O(log )？

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

Answer 2

您也可以使用static计数器(不需要更改函数的原型)：

public static long counter = 0;

public static long exponentiation(long x, int n){
    if(n == 0){
        return 1;
    }
    else if (n % 2 == 0){
        x = exponentiation(x, n / 2);
        counter++;
        return x * x; 
    }
    else{
        counter++;
        return x * exponentiation(x, n-1);
    }
}

但是，每次调用该函数之前，都需要重置计数器，即设置counter = 0。

理论分析

请注意，您需要到计数器来证明它在O(log(n))中。要证明复杂性，只需通过查看代码流来找到复杂性项。假设T(n)是计算x^n的乘法数。因此，根据编写的代码，T(n) = T(n/2) + 1 (如果n是偶数)和T(n) = T(n-1) + 1 (如果n是奇数)。现在，至少在两个连续的递归中，输入n是偶数。因此，最多只要求2 log(n)到达n = 0。因为，对于每个偶数输入，下一个输入将减半。因此，我们可以得出结论，该算法是在O(log(n))中实现的。