更好地猜测上限

Question

这是来自"算法的介绍"的问题,其编号为4.4-5并且描述如下:

使用递归树确定递推T(n)= T(n-1)+ T(n/2)+ n的良好渐近上界.使用替换方法验证您的答案.

我发现计算递归树的重复是很困难的.我给出的答案

Math.pow(2,n)的

看起来太松了.也许有更好的猜测存在.谢谢你的帮助.

Answer 1

希望我没有犯错:)

让我们 A(n)=T(n/2)+n

0. T(n)=T(n-1)+A(n)=T(n-2)+A(n-1)+A(n)=...=A(1)+A(2)+...+A(n)
   T(n)=sum[1..n]A(n)
   T(n)=sum[i=1..n]T(i/2)+sum[i=1..n]i

假设n/2是整数除法,T(n/2)=T((n+1)/2)对于偶数n,所以第一个和由两个相等的一半组成:T(1)+T(1)+T(2)+T(2)+...

1. T(n)=2*sum[1..n/2]T(i)+n*(n-1)/2

以来 T(n)<=T(m) for every n<=m

2. T(n)<=n*T(n/2)+n*(n-1)/2

以来 T(n/2)>=n/2>=(n-1)/2

3. T(n)<=n*T(n/2)+n*T(n/2)=2*n*T(n/2)

让我们只考虑这个n=2^k,因为T是单调的:n=2^k和U(k)=T(2^k)

4. U(k)<=2*(2^k)*U(k-1)=2^(k+1)*U(k-1)

让 L(k)=log2 U(k)

5. L(k)<=k+1+L(k-1)

就像我们在step0和step1之间做的那样

6. L(k)<=k*(k-1)/2+k=k*k/2-k/2+k<=k*k

7. U(k)=2^L(k)<=2^squared(k)

8. T(n)=U(log2 n)<=2^squared(log2 n)