以下程序的空间复杂度是否正确？

本文介绍了以下程序的空间复杂度是否正确？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 如果我们根据堆栈大小看到它将是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）; } 注意我在递归后清除内存解决方案 不要怀疑，确保。 定义一个全局变量，一个计数器， 这样代码你的代码 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 DOUBTS1)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 recursionWhat 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 解决方案 Don't doubt, make sure.Define a global variable, a counter,chanje your code this waytestfun(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 tocounter = 0;testfun(n);// at this point, counter contain the total memory allocated to arrays over recursion 这篇关于以下程序的空间复杂度是否正确？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！