algorithm - 对上限的更好猜测

Question

这是《算法导论》中的一道题，编号为4.4-5，描述如下：

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

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

数学.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)

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）。但我必须补充一点，它仍然与您已有的解决方案基本相同。

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

这与斐波那契数列的递归关系相同，并且按照这个问题的答案中的步骤，它的计算复杂度与黄金比例(1+sqrt(5))/2 = 1,618与 的幂相匹配n。

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

综上所述，我已经考虑过使用一些次指数函数来近似运行时间。这似乎不容易做到，正如我所说，我相信你已经找到了预期的答案。