用两个递归情况确定递归方法的Big 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)的情况会加快执行时间,但我不知道如何确定它的复杂性和它的证据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).我希望我的解释有所帮助.