对上界的更好猜测

Question

这是“算法入门”中的一个问题，其数字为4.4-5，描述如下：

用递归树确定递推T(n) = T(n-1) + T(n/2) + n.Use的一个较好的渐近上界，替代法验证你的答案。

我发现很难计算递归树的递归。我给出的答案

Math.pow(2，n)

似乎太loose.Maybe，有一些更好的猜测existed.Thanks提供任何帮助。

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)

Answer 2

递归关系似乎产生了一个次指数和超线性计算时间，这意味着任何选择的基都将作为一个上界工作，给定一个足够大的n。

您选择的2^n是一个很好的答案，可能是他们在书中寻找的答案。这是一个简单的解决方案，即使对于非常小的n值也是有效的。(不过，我理解您为什么要问这个问题，因为即使对于中等大的T(n)，它的增长也比n快得多。)

给定T(1) = 1 (或其他常量)，递归方程给出n前几个值的运行时间如下。

T(1) = 1          n^1 = 2
T(2) = 4          n^2 = 4
T(3) = 11         n^3 = 8
T(4) = 19         n^4 = 16
T(5) = 35         n^5 = 32
T(6) = 52         n^6 = 64
T(7) = 78         n^7 = 128
T(8) = 105        n^8 = 256
T(9) = 149        n^9 = 512

我们可以看到，选择2^n作为上限对于所有值T(6)及以上都是有效的。

如果您想要一个比2^n更低的界限，您可以选择一个较低的基数(通过权衡，它只对较高数量的n有效)。但我必须补充一点，这基本上仍将是你已有的解决办法。

任何比一个大的基都可以，但是更具体一点，例如，我们可以看到递归方程T(n) = T(n-1) + T(n/2) + n被n>5的方程T(n) = T(n-1) + T(n-2)所限制。

这是与Fibonacci序列相同的递归关系，按照this问题答案中的步骤，它具有一个计算复杂度，将黄金比率(1+sqrt(5))/2 = 1,618与n的幂相匹配。

绘制我们可以看到的n的实际值，T(n)的值以((1+sqrt(5))/2)^n为界。从图中看，它似乎是值n=13及以上。

​

​

所有这一切，我已经考虑了一些关于用一些次指数函数来逼近运行时间。这似乎是不容易做到的，正如我说的，我相信你已经找到了预期的答案。