解释这些函数的复杂性是什么？

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)。