如何求解递推方程T(N)=T(n/2)+T(n/4)+\θ(N)？

Question

如何求解递归方程

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

2.T(1)=1

使用Big-Theta表示法给出结果

Answer 1

我不想给你直接的答案，但我的提示是:寻找形式的数学级数：

1/2 + 1/4 + ... + 1/2^n

Answer 2

好的，然后我们看这个问题，我们可以分析它。

让我们从例子开始，当我们探索它们时，我们可以更好地理解如何解决它们(另一个问题是如何表示我们拥有的数据，但这是一个计算机科学，知道如何表示数据是可读的)。(提示，任何小于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。

现在让我们检查一下上面的teta

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)

你看到它的线性了吗？

你能从这里走出来吗？

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

祝好运,

别忘了下限分析。