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