解釋這些函數的複雜性是什麼？

Question

我想知道如何找到使用T（n）這些函數的複雜性..和這樣的東西..因爲我只能猜測。
第一個功能：

int f(int n) 
{ 
if (n == 1) 
     return 1 ; 
    return 1 + f(f(n-1)); 
} 

時間&空間的複雜性？


第二功能：

時間函數f &空間複雜度（）??? ：

void f(int n) 
{ 
    int i ; 
    if(n < 2) return ; 
    for(i = 0 ; i < n/2 , i+= 5) 
     printf("*"); 
    g(n/3); 
    g(n/3); 
} 


void g(int n) 
    { 
     int i ; 
     for(i = 0 ; i < n ; i++) 
     printf("?") ; 
     f(3*n/2); 
    } 

非常感謝:)

Answer 1

它可能會讓你大吃一驚，但第二個是比較容易下手。 O_O IKR

---

二級功能：

g(n) = n + f(3n/2)，f(n) = n/10 + 2g(n/3)。因此f(n) = 21n/10 + 2f(n/2)。

替代n = 2^m，因此f(2^m) = 21(2^m)/10 + 2f(2^(m-1)) = 2*21(2^m)/10 + 4f(2^(m-2))等等

的第一項款項m*21(2^m)/10，這可能是明顯的給你。

第二項（與f（））幾何增長;現在f(1) = 1（因爲只有1次操作），所以如果你擴展到最後一期，你會發現這個術語是2^m * f(1) = 2^m。因此，f的總複雜度是f(2^m) = m*21(2^m)/10 + 2^m或f(n) = n(2.1*log(n) + 1)，其中log是以2爲底的對數。

因此f(n)是O(n log(n))。

---

第一功能：

好，我會說實話，我不知道如何下手，但我用C測試的代碼++和結果是完全f(n) = n。

證明是用歸納：

• 假設f(n) = n，然後f(n + 1) = 1 + f(f(n)) = n + 1。因此，如果對於n是正確的，那麼對於n + 1也是如此。顯然，f(1) = 1顯然是
• 。所以對於2和3,4,5 ......等都是如此。

因此通過數學歸納，f(n) = n。

現在的時間複雜度位。由於f(n)返回n，嵌套的f(f(n-1))中的外部調用實際上將是第二個調用，因爲參數相同：f(n-1); f(n-1);。因此T(n) = 2*T(n-1)並因此T(n) = 2^n。 O(2^n)。