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 为 log(n) 时，结果为 O(n): O(F(n))，这意味着当 n % 2 != 时，O(F(n)) 0 是 O(n) + O(log(n))，或者简单地 O(n)