以下程序的空间复杂度是否正确？ [英] Is the space complexity of below program is correct?

问题描述

如果我们根据堆栈大小看到它将是O（n），我必须计算此函数的空间复杂度，但是在每次递归调用中，两个数组都消耗额外的空间，即2n或O（n）



MY DOUBTS



1）当我们计算此函数的时间复杂度时，过程将如下所示：每个递归调用O（n）额外空间由两个数组占用（我只取2n的顺序），因为堆栈大小为O（n），那么空间复杂度为O（n ^ 2）



2）如果我用2d数组替换这两个数组会发生什么，然后在每次递归调用O（n ^ 2）时会占用额外的空间，因为堆栈大小是O（n）然后是空格这个时间的复杂性将是O（n ^ 3）



注意这个函数没有什么特别的，只计算空间复杂度会留下垃圾值，因为我在递归后没有释放内存



我的尝试：

 testfun（n）{
 if（n == 0）
返回; 
 
 int * a = malloc（sizeof（int）* n）; 
 int * b = malloc（sizeof（int）* n）; 
 for（int i = 0; i< n; i ++）
 {a [i] = n + 2 * i; 
 b [i] = n + 3 * i; 
} 
 
 testfun（n-1）; 
免费（a）; 
免费（b）; 
 
} 

注意我在递归后清除内存

解决方案

这样一个函数，当 N 增长时，你可以放心地忽略堆栈分配占用的空间。

在堆上，由于你有递归调用

记忆（N）= 2 * N + .. + 4 + 2 

即

内存（N）= 2 * N！

（当然以 sizeof（int）衡量）。

所以函数空间复杂度是

 O（N！）
 

对不起，我犯了一个大错（非常感谢 Patrice T 发现它）。我实际上乘以我要添加的东西。

所以

内存（N）= N（N + 1）

和函数空间的复杂性是

 O（N ^ 2）

< blockquote>

Quote：

MY DOUBTS

不要怀疑，确保。

定义一个全局变量，一个计数器，

这样代码你的代码

 testfun（n）{
  if （n ==  0 ）
  return ; 
 
  int  * a = malloc（ sizeof （ INT ）* N）; 
 计数器+ = n;  
  int  * b = malloc（ sizeof （ int ）* n）; 
 计数器+ = n;  
  （ int  i =  0 ; i< n; i ++）
 {a [i] = n + 2 * i; 
 b [i] = n + 3 * i; 
} 
 
 testfun（n-  1 ）; 
免费（a）; 
免费（b）; 
 
} 

然后，将函数调用更改为

 计数器=  0 ;  
 testfun（n）; 
  //  此时，计数器包含通过递归分配给数组的总内存 

I have to calculate space complexity for this function if we see according to stack size then it will be O(n) but in every recursive call two arrays are consuming extra space that is 2n or of order O(n)

MY DOUBTS

1)When we calculate time complexity for this function the process will be as follows as in every recursive call O(n) extra space is taken by two arrays(I am taking only order of 2n ) and since stack size is O(n) then space complexity is O(n^2)

2) what will happen if i replace these two arrays with a 2d array then in every recursive call O(n^2) extra space will be taken and since stack size is O(n) then space complexity this time will be O(n^3)

NOTE Nothing special about this function only calculating space complexity leave the garbage value since i am not freeing the memory after recursion

What I have tried:

testfun(n){
  if(n==0)
  return;

  int *a=malloc(sizeof(int)*n);
  int *b=malloc(sizeof(int)*n);
  for(int i=0;i<n;i++)
  {  a[i]=n+2*i;
     b[i]=n+3*i;
  }

  testfun(n-1);
  free(a);
  free(b);

  }

NOTE I am clearing memory after recursion

解决方案

With such a function, when N grows, you can safely ignore the space taken by stack allocation.
On the heap, due to the recursive calls you have

memory(N) = 2*N + .. + 4 + 2

that is

memory(N) = 2*N!

(measured in sizeof(int), of course).
So the function space complexity is

O(N!)

Sorry I made a blunder (many thanks to Patrice T for spotting it). I actually multiplied what I have to add instead.
So

memory(N) = N(N+1)

And function space complexity is

O(N^2)

Quote:

MY DOUBTS

Don't doubt, make sure.
Define a global variable, a counter,
chanje your code this way

testfun(n){
  if(n==0)
  return;

  int *a=malloc(sizeof(int)*n);
  counter += n;
  int *b=malloc(sizeof(int)*n);
  counter += n;
  for(int i=0;i<n;i++)
  {  a[i]=n+2*i;
     b[i]=n+3*i;
  }

  testfun(n-1);
  free(a);
  free(b);

  }

then, change function call to

counter = 0;
testfun(n);
// at this point, counter contain the total memory allocated to arrays over recursion

这篇关于以下程序的空间复杂度是否正确？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！