递归关系树法紧界
Recurrence relation tree method tight bound
我试图找到这个递归的渐近紧界：
T(n) = T(n/2)+T(2n/4)+n
我正在使用递归树方法来这样做，但我在最后迷路了，希望得到任何指导。
T(n/2) = T(n/4)+T(n/4)+n/2
T(2n/4) = T(n/2) 所以它也是 T(n/4)+T(n/4)+n/2
T(n/4) = T(n/8)+T(n/8)+n/4
树：
n
T(n/2) 和 T(2n/4)
T(n/4) 和 T(n/4) 和 T(n/4) 和 T(n/4)
直到所有的 T(1)
在第 1 级，有 1 次重复。在 2 级，有 1 次复发。
根的成本是 n。
级别 1 的成本为 n。
级别 2 的成本是 n.
我知道深度 = n/(2^k) = 1 所以 k = logbase2(n).
但是，我对这之后该做什么感到困惑。我将如何继续解决这个问题以找到它的严格界限？
你已经掌握了所有的部分，只是了解递归树方法。要找到总成本，您可以将树的每个级别的每个节点（子问题）的成本相加以获得每个级别的成本，然后对每个级别的成本求和以获得总成本。
您发现每个级别的成本始终是 n，因为深度 i 的节点数对于 0, 1, ... k 中的 i 是 2^i。在深度i，每个节点的成本如你所说的是n/(2^i) * T(1)。因此，由于 k = log2(n) - 1 是最大深度，我们得到 n 的 0, 1, ... log2(n) - 1 中 i 的总和。
总计 (n log2 n) * T(1)，由于 T(1) 是 ϴ(1) 中的常数，我们得到 T(n) ∈ ϴ(n log2 n)。这通常写成 ϴ (n log n) 而不指定底数，因为 log2 x ~ log10 x ~ ln x 被常数倍数分隔，并且渐近等价于任何其他底数大于 1 的对数。
我试图找到这个递归的渐近紧界： T(n) = T(n/2)+T(2n/4)+n
我正在使用递归树方法来这样做，但我在最后迷路了，希望得到任何指导。
T(n/2) = T(n/4)+T(n/4)+n/2
T(2n/4) = T(n/2) 所以它也是 T(n/4)+T(n/4)+n/2
T(n/4) = T(n/8)+T(n/8)+n/4
树：
n
T(n/2) 和 T(2n/4)
T(n/4) 和 T(n/4) 和 T(n/4) 和 T(n/4)
直到所有的 T(1)
在第 1 级，有 1 次重复。在 2 级，有 1 次复发。 根的成本是 n。 级别 1 的成本为 n。 级别 2 的成本是 n.
我知道深度 = n/(2^k) = 1 所以 k = logbase2(n).
但是，我对这之后该做什么感到困惑。我将如何继续解决这个问题以找到它的严格界限？
你已经掌握了所有的部分，只是了解递归树方法。要找到总成本，您可以将树的每个级别的每个节点（子问题）的成本相加以获得每个级别的成本，然后对每个级别的成本求和以获得总成本。
您发现每个级别的成本始终是 n，因为深度 i 的节点数对于 0, 1, ... k 中的 i 是 2^i。在深度i，每个节点的成本如你所说的是n/(2^i) * T(1)。因此，由于 k = log2(n) - 1 是最大深度，我们得到 n 的 0, 1, ... log2(n) - 1 中 i 的总和。
总计 (n log2 n) * T(1)，由于 T(1) 是 ϴ(1) 中的常数，我们得到 T(n) ∈ ϴ(n log2 n)。这通常写成 ϴ (n log n) 而不指定底数，因为 log2 x ~ log10 x ~ ln x 被常数倍数分隔，并且渐近等价于任何其他底数大于 1 的对数。