0

我正在解决一个代码,我的递归函数变成了这样->

int rec(n)
{

  if(n>=(n/2+n/3+n/4))
  {
      return n;
  }


  else
  {

     return  rec(n/2) + rec(n/3) + rec(n/4); 

  }

}

我想知道这个函数的时间复杂度是多少?

我认为递归关系将是-

T(n) = T(n/2) + T(n/3) + T(n/4) + f(n)

如何解决这种递归关系?在这种情况下 f(n) 的值是多少?

另外,如何将其转换为动态编程?

我编写的将其转换为动态的代码是-

    long long  rec(long long n)
{
    long long c[n]; // The number range is between 1 to 10^9


    for(int i=0;i<n;i++)
    c[n]=0;


    if(n>=(n/2+n/3+n/4))
    {
        c[n]=n;
        return n;
    }
    else
    {
        if (c[n]==0)
        c[n]=c[n/2]+c[n/3]+c[n/4];
        return c[n];
    }

}

但是,将递归转换为动态后,我的程序拒绝显示正确答案。我认为我没有正确地将其转换为动态编程。你能指导我如何去做吗?

谢谢

4

1 回答 1

1

if (n >= (n/2 + n/3 + n/4)) 基本上等价于 if (n <= 0)。n 不能小于 0,所以写 if (n == 0) return n 就可以了;这意味着时间复杂度由以下递归方程给出:

T(0) = 1
T(n) = T(n/2) + T(n/3) + T(n/4)

由于问题在较小问题中的划分不是对称的(并且因为 n/2 + n/3 + n/4 = 13n/12,大于 n)在第一次近似(一个大问题)中我会说 O (nlogn) 和 O(n^2)。我试图证明它是 O(nlog2n) 但没有签出(通过 log2n 我的意思是登录 n 的基数 2):

T(n) <= cnlog2n

从现在开始我只写logn

T(n) <= cn/2*logn/2 + cn/3*logn/3 + cn/4*logn/4
      = cn/2*logn - cn/2*log2 + cn/3*logn - cn/3*log3 + cn/4*logn - cn/4*log4
      = cn/2*logn - cn/2 + cn/3*logn - cn/3*log3 + cn/4*logn - cn/2
      = 13/12*cn*logn - cn(log3/3 - 1) 

不小于或等于cnlogn

O(n^2) 可以被证明是这样的:

if T(n) = O(n^2) then T(n) <= cn^2
T(n) <= c(n/2)^2 + c(n/3)^2 + c(n/4)^2
      = cn^2/4 + cn^2/9 + cn^2/16
      = 15cn^2/36 <= cn^2

所以 O(n^2) 假设是正确的,但它可能不是很准确。您可以尝试 O(nlogn) 和 O(n^2) 之间的另一个假设,看看它们是否像我上面所做的那样是正确的。

于 2013-05-03T17:51:16.477 回答