求出递归T(n)= T(n/2)+ T(n/4)+ T(n/8)？

Question

我正在努力解决复发问题T(n) = T(n/8) + T(n/2) + T(n/4).

我认为首先尝试使用递归树方法,然后将其用作我对替换方法的猜测是个好主意.

对于树,因为在非叶级别没有工作,我认为我们可以忽略它,所以我试图在叶子的#上面提出一个上限,因为这是唯一相关的东西.

我认为树的高度是最长的路径T(n/2),它产生的高度为log2(n).那么我想树完成后,与各级充满(即我们有3T(n/2)),所以我们必须3^i在每一个级别的节点,所以n^(log2(3))离开.T(n)然后将O(n^log2(3)).

不幸的是,我认为这是一个不合理的上限,我想我已经让它有点太高了......关于如何解决这个问题的任何建议？

Answer 1

您可以在这里使用的一个技巧是根据另一个变量重写重复.我们假设你写n = 2 ^k.然后复发简化为

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

设S(k)= T(2 ^k).这意味着您可以将此重复重写为

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

假设基本情况是S(0)= S(1)= S(2)= 1,为简单起见.鉴于此,您可以使用各种方法来解决此问题.例如,湮灭方法(链接的第5部分)在这里很好用于解决这种复发,因为它是线性递归.如果你在这里使用消灭器方法,那你就明白了

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

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

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

如果你找到等式E ³ - E ² - E - 1的根,那么你可以将递归的解作为线性组合,将这些根提升到k的幂.在这种情况下,事实证明,复发类似于为Tribonacci数字,如果你解决一切,你会发现,解决了复发的形式O(1.83929的东西^ķ).

现在,因为你知道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 ...})明显弱于此值.

希望这可以帮助!