首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >“嵌套”递归函数的时间和空间复杂度

“嵌套”递归函数的时间和空间复杂度
EN

Stack Overflow用户
提问于 2018-09-26 22:30:36
回答 1查看 679关注 0票数 1

在先前的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)。

我的问题是:

  • 为什么我们可以将f1(f1(n - 3))看作f1(n-3)+f1(n-3)或者2f1(n-3)?
  • 如果函数没有返回n而是改变了它,例如:返回n/3而不是返回n,那么我们该如何解决它?我们是否将其视为2f1((n-3)/3)?
  • if我们不能总是将f1(f1(n - 3))视为f1(n-3)+f1(n-3)或2f1(n-3)那么我们如何绘制递归树以及如何使用归纳方法T(N)编写和求解它?
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 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

  • If函数没有返回n,而是改变了它,例如:返回n/3而不是返回n,那么我们该如何解决它?我们是否将其视为2f1((n-3)/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,那么您将需要一个递归树,而不是简单的扩展。这取决于具体的问题,不用说。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52520165

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档