gpt4 book ai didi

c - 这个程序的空间复杂度是多少?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:46:18 25 4
gpt4 key购买 nike

这只是一个计算空间复杂度的测试函数,如果我们考虑堆栈帧的数量比 o(n) 多,但是 for 循环和 2-d 中的那些数组 a 和 b 又如何呢,我的教授告诉我们,它们在每次递归调用中也会占用一些内存空间复杂度是堆栈帧的大小,但它也在 for 循环中消耗了一些空间我应该同时考虑堆栈框架、两个数组和二维数组,还是应该优先考虑其中的任何一个,为什么?

I am just focusing on space complexity so forget about the result or garbage collection

testfun(n){
if(n==0)
return;
int c[10][10];
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;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
c[i][j]=1;
}
testfun(n-1);
free(a);
free(b);
}

最佳答案

您可能会想到 free 功能。但是,递归发生在这些 free 函数之前。因此,在函数的每次调用中,根据输入的值(i),分配的空间大小为2i。由于停止时间在 n == 0 上,总空间复杂度为 sum_{i = 1}^{n} 2*i = 2*n(n+1)/2 =\Theta(n^2).

关于c - 这个程序的空间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52904473/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com