如何解决复发。T(n)。= T(n-1) + T(n/2) + n？

Question

我知道要通过递归树方法获得运行时间，我们需要画一棵树并找到：

a) 树的层数.

由于树的左侧尺寸减小了 1，因此它是从根开始的最长路径。第 i 层的子问题大小为 n-i 。当大小达到 1 时，设置 n - i = 1，我们得到级别数，i = n - 1。

b) 树中每个节点的成本 : cn

c) 第 i 层的节点数: ：这就是我被困住的地方。无法找到第 i 层的节点，因为左侧减少 1，右侧减少一半。当然，左边的树更密。并非每个节点都会有两个子节点。

如果我能得到 c 的答案，我可以计算 T(n) = 0 级成本 + 1 级成本 + 2 级成本 + ...n-1 级的成本。如果 y1 是第 1 层的节点数，y2 是第 2 层的节点数，依此类推...然后
=> T(n) = cn + y1 * cn + y2 * cn + y3 * cn + ....yn-1 * cn 以获得总成本。

谁能指导我采取的方法？这是对的吗 ？我可以假设对于足够大的 n，我们可以忽略 T(n/2) 然后继续吗？。

网上搜索让我很困惑。问题是来自 CLRS 的 4.4-5。

请参见 这里

该解决方案表示 T(n) = O(2^n) 和 T(n) = omega(n^2) 并且没有解释如何实现。

另请参阅 这里

该解决方案表示 T(n) = O(n^2)。但与上述解决方案相矛盾

Answer 1

让 $S(n) = T(n) - 2n - 2$. 。你可以检查一下 $S(n) = S(n-1) + S(n/2)$ （忽略了一个事实 $n/2$ 不必是整数）。这表明添加剂 $n$ 术语没有太大区别。

对于大型 $n$, ，我们大致有 $S(n) - S(n-1) \大约 S'(n)$, ，所以我们需要求解微分方程$$ s'（n）= s（n/2）。$$考虑 $f(n) = \exp ( frac{1}{2}\log_2^2 n)$. 。然后$$ f'（n）= exp（ tfrac {1} {2} {2} log_2^2 n） cdot frac frac { ln n} {（ ln 4）n}，$$然而$ f（n/2）= exp（ tfrac {1} {2}（ log_2 n -1）^2） Exp（ - log n）= exp（ tfrac {1} {2} {2} log^2 n） cdot frac frac {1} {n}。$$这表明，至少， $\ln S(n) = heta(\log^2 n)$.

这是从哪里来的？你可以想到 $S(n)$ （有适当的基本情况！）作为从 $n$ 通过应用两个操作将其归零：减去 1 再除以 2。一个“典型的”这样的序列将大致包含 $\log_2n$ 许多第二类型的操作， $\θ(n)$ 操作总数，导致非常粗略的估计 $\binom{ heta(n)}{\log_2 n}$, ，其形式也为 $\exp heta(\log^2 n)$.

---

为了具体起见，请考虑以下精确定义 $S(n)$: ：基本情况是 $S(0) = 1$, ，并且对于 $n > 0$, $$ s（n）= s（n-1） + s（ lfloor n/2 rfloor）。$$这是顺序 A000123. 。高德纳, 几乎线性的递归, ，表明$$ log_4 s（n） sim log_4^2 n，$$也就是说，两项之比趋于 1，如下所示 $n \到 \infty$. 。OEIS 条目包含更精确的渐近线。

Answer 2

我不同意斐波那契催眠法，但我不能百分百确定我的答案

你看$ T(n)= T(n-1) +c*n = O(n ^2) $

$ T(n) = T(n/2) + c*n =O(n log n) $

然而，你不能通过直接相加得到你的T(n)。

如果你在递归中前进一级（你可以画一棵树）

t（n）= t（n-2） + t（（n-1）/2） + t（n/2-1） + t（n/4） + [n +（n-1） +（n -1）/2 +（N/2-1） + N/4

这向你展示它不仅仅是 $ O(n^2) $

我必须完成它，但我怀疑 $ O((n^2) * log n) $或者 $ O((n^2) * n ^ {log n} ) = O(n^3) $

{有一个项 n(1+1/2+1/4+..1/n) 以 log n 步衰减，我必须再次检查}