这种相互递归代码的java时间复杂性

Question

我有一段java中的递归代码，我想知道这段代码的时间复杂度是多少。不过我的猜测是O（2^n），因为对于G方法，return（n-1）+G（n-1）在每次调用中分裂为2。或者这是O（n）部分？我对此不确定

public static int F(int n)
{
    if (n <= 1)
        return 1;
    else if (n % 2 == 0)
        return n + F(n/2);
    else
        return G(n-1)-n;
}

public static int G(int n)
{
    if(n <= 1)
        return 1;
    else if (n % 2 == 0)
        return F(n-1) + G(n-1);
    else
        return F(n-3);
}

Answer 1

你可以用F重写G

public static int G(int n) {
    if(n <= 1)
        return 1;
    else if(n % 2 == 0)
        return F(n-1) + F(n-4);
    else
        return F(n-3);
}

这可以让你用F重写F

public static int F(int n) {
    if(n <= 1)
        return 1;
    else if(n % 2 == 0)
        return n + F(n/2);
    else
        return F(n-2) + F(n-5);
}

当n%2==0时，结果是O（n）：O（F（n））是log（n），这意味着当n%2！=0是O（n）+O（log（n）），或者干脆O（n）