问求解递推关系: T(n)=T(n-1)+T(n/2)+n

EN

对于CS类来说，这是一个非常奇怪的重复。这是因为从一个角度来看：T(n) = T(n-1) + T(n/2) + n大于T(n) = T(n-1) + n，即O(n^2)。

但从另一个角度看，函数方程 有一个精确的解决方案：T(n) = -2(n + 2)。您可以很容易地看到，通过将它替换回方程：-2(n + 2) = -2(n + 1) + -(n + 2) + n，这是精确的解。我不知道这是否唯一的解决办法。

我就是这样得到它的：T(n) = T(n-1) + T(n/2) + n。因为您计算的是非常大的n，而n-1几乎与n相同。所以你可以把它重写为T(n) = T(n) + T(n/2) + n，它是T(n/2) + n = 0，它等于T(n) = - 2n，所以它是线性的。这违背了我的直觉(这里的减号)，但是有了这个解决方案，我尝试了T(n) = -2n + a并找到了a的值。

我相信你是对的。递推关系总是分裂为两个部分，即T(n-1)和T(n/2)。从这两个方面来看，很明显，n-1的下降速度比n/2慢，换句话说，树的n-1部分会有更多的分支。尽管如此，在考虑大o时，只考虑“最坏情况”的情况是有用的，在这种情况下，树的两边减少n-1 (因为这减少得更慢，所以需要更多的分支)。总之，您需要将关系分成两部分，总共n次，因此您正确地说O(2^n)。

你的推理是正确的，但你付出的太多了。(例如，说2x^3+4=O(2^n)也是正确的，但这并不像2x^3+4=O(x^3)那样提供信息。)

我们要做的第一件事是去掉非齐次项n。这表明我们可以寻找T(n)=an+b形式的解决方案。用它来代替，我们会发现：

an+b = a(n-1)+b + an/2+b + n

这会减少到

0 = (a/2+1)n + (b-a)

暗示着a=-2和b=a=-2。因此，T(n)=-2n-2是方程的一个解。

我们现在想通过减去我们已经找到的解决方案来找到其他的解决方案。让我们定义U(n)=T(n)+2n+2。然后方程变成

U(n)-2n-2 = U(n-1)-2(n-1)-2 + U(n/2)-2(n/2)-2 + n

这会减少到

U(n) = U(n-1) + U(n/2).

U(n)=0是这个方程的一个明显的解，但是这个方程的非平凡解是如何表现的呢？

让我们假设U(n)∈Θ(n^k)代表一些k>0，所以U(n)=cn^k+o(n^k)。这就使得方程

cn^k+o(n^k) = c(n-1)^k+o((n-1)^k) + c(n/2)^k+o((n/2)^k)

现在，(n-1)^k=n^k+Θ(n^{k-1})，使上面的内容变成

cn^k+o(n^k) = cn^k+Θ(cn^{k-1})+o(n^k+Θ(n^{k-1})) + cn^k/2^k+o((n/2)^k)

吸收低阶项并减去常见的cn^k，我们得出

o(n^k) = cn^k/2^k

但这是错误的，因为右手的生长速度比左边快。因此，U(n-1)+U(n/2)比U(n)增长得更快，这意味着U(n)必须比我们假定的Θ(n^k)增长得更快。因为对于任何k来说都是这样，所以U(n)必须比任何多项式增长得更快。

指数函数是比任何多项式增长更快的东西的一个很好的例子。因此，让我们假设U(n)∈Θ(c^n)对于某些c>1，所以U(n)=ac^n+o(c^n)。这使得方程ac^n+o(c^n) =ac^{n-1}+o(c^n-1})+ac^{n/2}+o(c^n/2})重新排列，并使用一定的增长数学阶数，这成为

c^n = o(c^n)

这是错误的(再次)，因为左手的生长速度比右边快。因此，U(n)比U(n-1)+U(n/2)增长得更快，这意味着U(n)的增长必须比我们假定的Θ(c^n)慢。因为对于任何c>1来说都是这样，所以U(n)的增长必须比任何指数都慢。

这使我们进入准多项式的领域，其中ln U(n)∈O(log^c n)，和次指数，ln U(n)∈O(n^ε).这两种方法中的任何一种都意味着我们想要查看L(n):=ln U(n)，在前面的段落中，这意味着L(n)∈ω(ln n)∩o(n)。取我们方程的自然对数，我们有

ln U(n) = ln( U(n-1) + U(n/2) ) = ln U(n-1) + ln(1+ U(n/2)/U(n-1))

或

L(n) = L(n-1) + ln( 1 + e^{-L(n-1)+L(n/2)} ) = L(n-1) + e^{-(L(n-1)-L(n/2))} + Θ(e^{-2(L(n-1)-L(n/2))})

所以一切都归结为：L(n-1)-L(n/2)的增长有多快？我们知道L(n-1)-L(n/2)→∞，因为否则L(n)∈Ω(n)。而且L(n)-L(n/2)可能也同样有用，因为L(n)-L(n-1)∈o(1)比L(n-1)-L(n/2)小得多。

不幸的是，这是我所能解决的问题。我看不到控制L(n)-L(n/2)增长速度的好方法(我已经盯着这个看了好几个月了)。最后，我可以引用另一个答案：“CS类非常奇怪的递归”。