这些功能的复杂性如何解释？

Question

我想知道如何使用 T(n) 找到这些函数的复杂性......以及类似的东西......因为我只能猜测。
第一个函数：

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

时间&Space复杂度??

第二个函数：

time&space 函数 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 伊克尔

第二个函数：

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) returns n，嵌套 f(f(n-1)) 中的外部调用实际上是第二次调用，因为参数相同：f(n-1); f(n-1);。因此 T(n) = 2*T(n-1)，因此 T(n) = 2^n。 O(2^n).

这些功能的复杂性如何解释？

What is the complexity of these functions with explanation?

algorithm

performance

complexity-theory

time-complexity