java - 用两个递归案例确定递归方法的大 O？

Question

我目前正在努力计算一个递归指数函数的 Big O，该函数在 n%2 == 0 时采用快捷方式。代码如下:

public static int fasterExponent(int x, int n){
    if ( n == 0 ) return 1;
    if ( n%2 == 0 ){
        int temp = fasterExponent(x, n/2);
        return temp * temp;
    }
    return x * fasterExponent(x, --n); //3
}

我知道，如果没有 (n%2 == 0) 的情况，这个递归指数函数将是 O(n)。包含 (n%2 == 0) 案例加快了执行时间，但我不知道如何确定它的复杂性及其 witness c 的值。

Answer 1

答案是 O(log n)。

原因 fasterExponent(x, n/2) 这会将每一步的输入减半，当它达到 0 时我们就完成了。这显然需要 log n 个步骤。但是 fasterExponent(x, --n); 呢？我们在输入为奇数时执行此操作，在下一步中它将为偶数，然后我们回到 n/2 的情况。让我们考虑每次将 n 除以 2 时都必须执行此操作的最坏情况。好吧，每次执行第一个递归步骤时，我们都会执行第二个递归步骤一次。所以我们需要 2 * log n 个操作。那仍然是 O(log n)。希望我的解释对您有所帮助。