在先前的cs介绍考试中,有一个问题:计算函数f1的空间和时间复杂度作为n的函数,假设malloc(n)的时间复杂度为O(1),其空间复杂度为O(n)。
int f1(int n) {
if(n < 3)
return 1;
int* arr = (int*) malloc(sizeof(int) * n);
f1(f1(n – 3));
free(arr);
return n;
}
官方的解决方案是:时间复杂度: O(2^(n/3)),空间复杂度: O(n^2)
我试着解决它,但我不知道如何解决,直到我在笔记本上看到一个笔记:由于函数返回n,那么我们可以将f(f(n-3))视为f(n-3)+f(n-3)或2f(n-3)。在这种情况下,问题变得与这个问题非常相似:Space complexity of recursive function
我试着用这种方法解题,得到了正确的答案。
对于时间复杂度:
T(n)=2T(n-3)+1,T(0)=1
T(n-3)=2T(n-3*2)+1T(N)=2*2T(n-3*2)+2+1
T(n-3*2)=2T(n-3*3)+1T(N)=2*2*2T(n-3*3)+2*2+2+1
..。
T(n)=(2^k)T(n-3*k)+2^(k-1)+...+2^2+2+1
n-3*k=0
k=n/3 ===> 2^(n/3)+...+2^2+2+1=2^(n/3)1+(1/2)+(1/2^2)+...=2^(n/3)*constant
因此我得到O(2^(n/3))
对于空间复杂度:树的深度是n/3,每次我们做malloc,我们得到(n/3)^2,因此O(n^2)。
我的问题是:
发布于 2018-09-26 22:42:53
我们可以把f1(f1(n - 3))看作f1(n-3)+f1(n-3)还是2f1(n-3)?
因为i)首先计算嵌套的f1
,它的返回值用于调用外部f1
;因此这些嵌套调用等同于:
int结果= f1(n - 3);f1(结果);
..。和ii) f1
的返回值只是它的参数(除了基本情况,但渐近无关紧要),因此上面的进一步等价于:
f1(n - 3);f1(n - 3);// result =n- 3
只有外部调用会受到影响。同样,使用前面的等效表达式:
f1(n - 3);/= (n - 3) /3 f1((n - 3) / 3);
我们不能总是将f1(f1(n - 3))视为f1(n-3)+f1(n-3)或2f1(n-3),那么我们如何绘制递归树,以及如何使用归纳方法T(N)编写和求解它?
您可以像上面那样将它们分成两个单独的调用,并且再次记住,只有第二个调用受返回结果的影响。如果这不同于n - 3
,那么您将需要一个递归树,而不是简单的扩展。这取决于具体的问题,不用说。
https://stackoverflow.com/questions/52520165
复制相似问题