求解递归T(n)= T(n/2)+ T(n/4)+ T(n/8)? [英] Solving the recurrence T(n) = T(n/2) + T(n/4) + T(n/8)?

问题描述

我正在尝试解决重复T(n) = T(n/8) + T(n/2) + T(n/4).

I'm trying to solve a recurrence T(n) = T(n/8) + T(n/2) + T(n/4).

我认为先尝试一种递归树方法，然后将其用作替代方法的猜测是一个好主意.

I thought it would be a good idea to first try a recurrence tree method, and then use that as my guess for substitution method.

对于这棵树，由于没有叶子的任何工作都没有完成，所以我认为我们可以忽略它，所以我试图在叶子的数量上设定一个上限，因为这是唯一相关的事情在这里.

For the tree, since no work is being done at the non-leaves levels, I thought we could just ignore that, so I tried to come up with an upper bound on the # of leaves since that's the only thing that's relevant here.

我考虑了走过T(n/2)的路径最长的树的高度，这产生了log2(n)的高度.然后，我假设树是完整的，所有级别都已填充(即，我们有3T(n/2))，因此我们在每个级别上都有3^i个节点，所以n^(log2(3))离开了.T(n)将是O(n^log2(3))

I considered the height of the tree taking the longest path through T(n/2), which yields a height of log2(n). I then assume the tree is complete, with all levels filled (ie. we have 3T(n/2)), and so we would have 3^i nodes at each level, and so n^(log2(3)) leaves. T(n) would then be O(n^log2(3)).

不幸的是，我认为这是一个不合理的上限，我认为我已经把它设置得太高了……关于如何解决这个问题的任何建议?

Unfortunately I think this is an unreasonable upper bound, I think I've made it a bit too high... Any advice on how to tackle this?

推荐答案

您可以在此处使用的一个技巧是用另一个变量来重写递归.假设您写n = 2 ^k .然后将重复次数简化为

One trick you can use here is rewriting the recurrence in terms of another variable. Let's suppose that you write n = 2^k. Then the recurrence simplifies to

T(2 ^k )= T(2 ^k-3 )+ T(2 ^k-2 )+ T(2 ^k-1 ).

T(2^k) = T(2^k-3) + T(2^k-2) + T(2^k-1).

让我们让S(k)= T(2 ^k ).这意味着您可以将此重复周期重写为

Let's let S(k) = T(2^k). This means that you can rewrite this recurrence as

S(k)= S(k-3)+ S(k-2)+ S(k-1)

S(k) = S(k-3) + S(k-2) + S(k-1).

为了简单起见，假设基本情况为S(0)= S(1)= S(2)= 1.有了这个，您就可以使用多种方法来解决这种重复现象.例如， an灭者方法(本节链接中的5)对于解决此递归非常有用，因为它是线性递归.如果您在这里使用the灭者方法，您将得到

Let's assume the base cases are S(0) = S(1) = S(2) = 1, just for simplicity. Given this, you can then use a variety of approaches to solve this recurrence. For example, the annihilator method (section 5 of the link) would be great here for solving this recurrence, since it's a linear recurrence. If you use the annihilator approach here, you get that

S(k)-S(k-1)-S(k-2)-S(k-3)= 0

S(k) - S(k - 1) - S(k - 2) - S(k - 3) = 0

S(k + 3)-S(k + 2)-S(k + 1)-S(k)= 0

S(k+3) - S(k+2) - S(k+1) - S(k) = 0

(E ³ -E ² -E-1)S(k)= 0

(E³ - E² - E - 1)S(k) = 0

如果找到方程式E ³ -E ² -E-1的根，则可以将递归解写为方程的线性组合根数提高到k的幂.在这种情况下，事实证明重复发生与Tribonacci数字相似，并且如果解决所有问题后，您会发现递归可以解决O(1.83929 ^k )形式的问题.

If you find the roots of the equation E³ - E² - E - 1, then you can write the solution to the recurrence as a linear combination of those roots raised to the power of k. In this case, it turns out that the recurrence is similar to that for the Tribonacci numbers, and if you solve everything you'll find that the recurrence solves to something of the form O(1.83929^k).

现在，由于您知道2 ^k = n，因此我们知道k = lg n.因此，递归求解为O(1.83929 ^{lg n} ).让我们让a = 1.83929.然后解的形式为O(a ^{lg n} )= O(a ^{(log _a n)/log _a 2)} )= O(n ^{1/log _a 2} ).这大约等于O(n ^{0.87914 ...} ).您的O(n ^{lg 3} )= O(n ^{1.584962501 ...} )的初始上限明显弱于此上限.

Now, since you know that 2^k = n, we know that k = lg n. Therefore, the recurrence solves to O(1.83929^{lg n}). Let's let a = 1.83929. Then the solution has the form O(a^{lg n}) = O(a^{(log_a n) / log_a2)}) = O(n^{1/log_a 2}). This works out to approximately O(n^0.87914...). Your initial upper bound of O(n^{lg 3}) = O(n^{1.584962501...}) is significantly weaker than this one.

希望这会有所帮助！

这篇关于求解递归T(n)= T(n/2)+ T(n/4)+ T(n/8)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！