我正在解决一个代码,我的递归函数变成了这样->
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];
}
}
但是,将递归转换为动态后,我的程序拒绝显示正确答案。我认为我没有正确地将其转换为动态编程。你能指导我如何去做吗?
谢谢