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);
}

结果是 O(n): O(F(n)) 对于当 n % 2 == 0 是 log(n) 的情况，这意味着 O(F(n)) 当 n % 2 != 0 是 O (n) + O(log(n))，或者简单地O(n)