标签: recurrence

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

T(n) = T(sqrt(n)) + 0(1)

在第一个中,我使用n,logn等的替换方法; 都给了我错误的答案.
重复树:我不知道我是否可以申请,因为根将是一个常数.

有人可以帮忙吗？

我想用递推方程找出程序的时间复杂度.那是 ..

int f(int x)
{
if(x<1) return 1;
 else  return f(x-1)+g(x); 
}
int g(int x)
{
if(x<2) return 1;
 else return f(x-1)+g(x/2);
}

我写了它的递推方程并尝试解决它,但它继续变得复杂

T(n) =T(n-1)+g(n)+c
         =T(n-2)+g(n-1)+g(n)+c+c
         =T(n-3)+g(n-2)+g(n-1)+g(n)+c+c+c
         =T(n-4)+g(n-3)+g(n-2)+g(n-1)+g(n)+c+c+c+c
         ……………………….
        ……………………..
        Kth time …..
        =kc+g(n)+g(n-1)+g(n-3)+g(n-4).. .. . … +T(n-k)

Let at kth time input become 1
Then n-k=1
         K=n-1
Now i end up with this..
T(n)= (n-1)c+g(n)+g(n-1)+g(n-2)+g(n-3)+….. .. g(1)

我无法进一步解决它.如果我们计算这个程序中函数调用的数量,可以很容易地看出时间复杂度是指数级的,但我想用重复证明它.怎么做到呢 ？

在Anwer 1中的解释,看起来正确,我做过类似的工作.

这段代码中最困难的任务是写出它的递归方程.我已经绘制了另一个图,我确定了一些模式,我认为我们可以从这个图中得到一些帮助,可能是可能的递归方程.

And I came up with this equation , not sure if it is right ??? …

我想知道是否存在任何继续证明算法正确性的规则/方案？例如,我们在自然数上定义了一个函数$ F $,定义如下:

function F(n,k)
begin
  if k=0 then return 1
  else if (n mod 2 = 0) and (k mod 2 = 1) then return 0
  else return F(n div 2, k div 2);
end;

其中$ n\\ text {div}\2 =\left\lfloor\frac {n} {2}\right\rfloor $

任务是证明$ F(n,k)=\begin {cases} 1\Leftrightarrow {n\choose k}\\ text {mod}\2 = 1\0\text {otherwise}\end {cases} $

它看起来并不复杂(我错了吗？),但我不知道这种证据应该如何构建.我非常感谢你的帮助.

在遇到复发时,我遇到了忽略地板和天花板的地方.

CLRS (第4章,第83页)的例子,其中忽略了最低限度:

这里(第2 页,练习4.1-1)是一个忽略上限的例子:( 编辑:我从公众舆论中得知这有点可疑.)

事实上,在CLRS(第88页)中,它提到:

"解决复发问题时,地板和天花板通常无关紧要"

我的问题:

1. 这里"通常"是指所有情况？如果是的话,我可以一直忘记它们.
2. 如果没有,那么在解决复发问题时,地板和天花板何时真正算在内？

注意:这不是作业问题.当我刷新DS和算法时,我想到了这一点.

我的问题来自于"大O的简单英语解释".我不知道对数复杂性的确切含义.我知道我可以在时间和操作次数之间进行回归并计算X平方值,并确定复杂度.但是,我想知道一种在纸上快速确定它的方法.

您如何确定对数复杂度？有一些很好的基准吗？

如何确定在处理递归运行时构建的递归树的高度？它与确定常规树的高度有何不同？

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

编辑:对不起,我的意思是添加如何从递归关系中获取递归树的高度.

对不起大家!我的错!谢谢你的提醒,我发现f(0,k)== f(k,0)== 1.这个问题是关于如何计算从网格(0,0)到(m,n)的最短路径数).

我现在必须解决以下等式,确切地找出f(m,n)等于什么.

1) f(m,n) = 0 : when (m,n) = (0,0)
**2) f(m,n) = 1 : when f(0,k) or f(k,0)**
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else

例如:

1) f(0,0) = 0; 
2) f(0,1) = 1; f(2,0) = 1; 
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3  

我记得有一种标准的方法可以解决这种二进制递归方程,正如我几年前在算法类中学到的那样,但我现在还记不起来了.

任何人都可以提供任何暗示吗？或关键字如何找到答案？

我得到以下结论:

T(n) = T(n - 1) + n = O(n^2)

现在,当我解决这个问题时,我发现边界非常宽松.我做错了什么或是这样吗？

是否有可能解决递归关系

T(n)=√nT(√n)+ n

使用主定理？它不是形式

T(n)= a·T(n/b)+ f(n)

但这个问题是在CLRS第4章的练习中给出的.

因此,在之前的考试中,我被要求在不使用主定理的情况下求解以下递推方程:

T(n)= 9T(n/3) + n^2

不幸的是,我无法在考试中弄明白,所以我使用硕士定理解决了它,所以我可以知道答案(当然,我对这个问题没有任何赞誉),现在我想知道如何在没有主人定理的情况下解决它,因为在期末考试中,会有类似的问题.

如果有人可以提供一步一步的解决方案(有解释),那就太棒了,谢谢!