我正在尝试解决复发问题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))。
不幸的是，我认为这是一个不合理的上限，我想我把它定得太高了......关于如何解决这个问题的任何建议？
您可以在这里使用的一个技巧是根据另一个变量重写递归。假设您写 n = 2 k。然后递归简化为
T(2 k ) = T(2 k-3 ) + T(2 k-2 ) + T(2 k-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 3 - E 2 - E - 1)S(k) = 0
如果你找到方程 E 3 - E 2 - E - 1 的根，那么你可以将递归的解写成这些根的 k 次幂的线性组合。在这种情况下，结果证明递归类似于 Tribonacci 数，如果你解决所有问题，你会发现递归求解为 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... )的初始上限明显弱于这个上限。
希望这可以帮助！
有一种比@template 提出的更简单的方法。除了 Master 的定理，还有一个Akra-Bazzi 方法可以让你解决这种递归：
这正是你所拥有的。所以你的g(x) = 0,a1 = a2 = a3 = 1和b1 = 1/2,b2 = 1/4和b3= 1/8. 所以现在你必须解方程：1/2^p + 1/4^p + 1/8^p = 1。
解决它 p 大约是0.879。您甚至不需要求解积分，因为它等于0。所以你的整体复杂性是O(n^0.879).