求解递归关系：T（n）= T（n-1）+ T（n / 2）+ n

Question

求解：T（n）= T（n-1）+ T（n / 2）+ n。

我尝试使用递归树来解决这个问题。分别有两个分支T(n-1)和T(n/2)。 T(n-1)将进入更高的深度。所以我们得到O(2^n)。这个想法是否正确？

Answer 1

不，你的想法不正确。复杂性是O(n)我也不得不承认这个问题很难。

这是一个解决方案。 T(n) = T(n-1) + T(n/2) + n。因为你计算非常大的n的东西，比n-1几乎与n相同。所以你可以把它重写为T(n) = T(n) + T(n/2) + n

在这里我犯了一个错误，错误的解决方案开始了：

这是T(n) = 1/2 * T(n/2) + n/2。如您所见，这种递归的复杂性将比原始递归复杂得多。

请注意，你不能在这里使用Master's定理，因为a < 1。

您可以开始展开递归。

最后一次求和变换，因为它是几何级数。因此，递归将在某个时间停止，您可以选择某个时间点。我在T(1) = b时选择了它。这发生在n/2^k = 1或n = 2^k这意味着k = log n。

如果你将这个qazxsw poi替换为递归，你将得到最大的元素运行为qazxsw poi，因此这是这个等式的运行时间。

错误的结束，正确的开始

这是k，它等于O(n)，所以它是线性的。这对我来说是违反直觉的（这里是减号），但是凭借这个解决方案，我看到T(n/2) + n = 0 T(n) = - 2n的解决方案非常接近functional equation。

如果你将它插入等式中，你将看到，对于任何T(n)=T(n-1)+T(n/2)+n，它只有1关闭。所以解决方案仍然是-2n - 2

附：再一次，CS类的一个非常奇怪的递归。

Answer 2

我相信你是对的。递归关系将始终分为两部分，即T（n-1）和T（n / 2）。看看这两个，很明显n-1的值比n / 2慢，或者换句话说，你将从树的n-1部分得到更多的分支。尽管如此，在考虑big-o时，仅考虑“最坏情况”情况是有用的，在这种情况下，树的两侧减少n-1（因为这减少得更慢，你需要有更多的分支）。总之，你需要将关系分成两次，总共n次，因此你说O（2 ^ n）是正确的。

Answer 3

你的推理是正确的，但你放弃的太多了。 （例如，说n也是正确的，但这不像O(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)。这使得等式ac ^ n + o（c ^ n）= ac ^ {n-1} + o（c ^ {n-1}）+ ac ^ {n / 2} + o（c ^ {n / 2重新排列和使用一些增长数学的顺序，这变成了

c>1

这是错误的（再次），因为左手边比右边增长得快。因此，U(n)=ac^n+o(c^n)比c^n = o(c^n) 增长得更快，这意味着U(n)必须比我们假设的U(n-1)+U(n/2)增长更慢。由于任何U(n)都是如此，Θ(c^n)必须比任何指数增长更慢。

这使我们进入准多项式的领域，其中c>1和subexenentials，其中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)增长速度的好方法（我几个月来一直盯着这个）。我唯一可以结束的是引用另一个答案：“CS类的一个非常奇怪的递归”。

Answer 4

我想我们可以这样看待它：

L(n-1)-L(n/2)

如果我们应用主人定理，那么：

L(n)-L(n/2)

Answer 5

T(n)=2T(n/2)+n < T(n)=T(n−1)+T(n/2)+n < T(n)=2T(n−1)+n与Θ(n∗logn) < Θ(T(n)) < Θ(2n)相同，因为我们正在解决n的极大值。如果T(n)=T(n-1)+T(n/2)+n，T(n)=T(n)+T(n/2)+n只能是真的。这意味着T(n)=T(n)+T(n/2)+n