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

Question

我目前正在努力计算一个递归指数函数的大 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

很直观地看到，在每个阶段，您都将问题大小减少了一半。例如，要找到 x⁴，您会找到 x²（我们称其为 A），并且 return 结果为 A*一种。再次将 x² 本身分为 x 和 x.

将两个数的乘法视为原始运算，可以看出递归是：

T(N) = T(N/2) + O(1)
Solving this recurrence(using say the Master Theorem) yields:
T(N) = O(logN)

Answer 2

答案是O(log n)。

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

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

Determining the Big O of a recursive method with two recursive cases?

java

algorithm

recursion

big-o