這個互相遞歸的代碼的時間複雜度

Question

我在java中有這個相互遞歸的代碼，我不知道這段代碼的時間複雜度是多少。我的猜測是O（2^n），因爲對於G方法，在每次調用期間，返回（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.

方面改寫摹

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（ （n）= O（log（n））的情況下，當n％2 == 0時的情況爲F（n） ），或簡單地O（n）