algorithm - 如何求解递归方程T(n)=T(n/2)+T(n/4)+\Theta(n)？

Question

如何求解递归方程

1.T(n)=T(n/2)+T(n/4)+\Theta(n)

2.T(1)=1

使用Big-Theta符号给出结果

Answer 1

那么我们看看这个问题carfuley我们可以分析一下。

让我们从例子开始，当我们探索它们时，我们可以更好地理解如何解决它们(另一个问题是如何表示我们拥有的数据，但这是一台计算机，它知道如何表示数据以使其可读). (提示，任何低于 1 的值都舍入到 1

T(1) = 1

T(2) = 1 + 1

T(3) = T(1.5) + 1

T(4) = T(2) + 1

T(5) = T(2.5) + T(1.25)

T(2.5) = T(1.25) + 1

T(6) = T(3) + T(1.3333)

现在，如果我们进行循环，我们可以理解 1 和 2 之间的值可以取 2 的上限或 1 的下限。

作为一个提示，如果你证明当你取所有上界并得到你想要的 teta 时，如果你取你想要的所有下界 teta，那么你证明它受相同的 teta 限制。

p>

现在让我们检查一下上部的乳头

T(1) = 1

T(2) = 1 + 1

T(3) = T(2) + 1 = (1 + 1) +1

T(4) = T(2) + 1 = (1 + 1) +1

T(5) = T(3) + T(2) = (1 + 1 + 1) + (1 + 1)

T(6) = T(3) + T(2) = (1 + 1 + 1) + (1 + 1)

你看到它是线性的吗？

你能从中摆脱困境吗？

这就是您处理此类问题的方式。

祝你好运

不要忘记下限分析。