递归：T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n) ，T(n)的复杂度是多少？
Recurrence: T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n) , what is the complexity of T(n)?
如何求解递归方程。 T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n)。
如果我们有 (n) 而不是 Ω(n)，我可以解决它，但现在我无法解决它。请帮助我！
这样的下界似乎有点不寻常，但我相信我们可以使用强归纳法给出 T(n) 的下界。我从一个有根据的猜测开始，即递归会将 O(lg n) 的一个因子添加到 Ω(n) 界限，并使用强归纳法来验证这个猜测。让我们考虑最小化 Ω(n) 以实现整个递归的下界的情况。也就是说，我们假设n隐藏在Omega符号中的函数实际上是Θ(n):
Assume true for all values of n up to k:
I.H. : T(n) < cn lg n - dn (for n < k)
Prove that it is true for k also:
T(k) = T(k/2) + T(k/4) + T(k/8) + Θ(n)
(IH) T(k) = (k/2)lg(k/2) + (k/4)lg(k/4) + (k/8)lg(k/8) - 3dn + Θ(n)
T(k) = ck lg k - 3dn + Θ(n)
< ck lg k - dn as required
因为我们可以选择足够大的常数 d 来超过隐藏在 Theta 符号中的常数。由于 cn lg n 是 Ω(n lg n)，我们可以将其作为递归的下界。由于原文中的 Ω(n) 项，我相信这是我们可以给出的最严格的渐近界限。
如何求解递归方程。 T(n) = T(n/2) + T(n/4) + T(n/8) + Ω(n)。 如果我们有 (n) 而不是 Ω(n)，我可以解决它，但现在我无法解决它。请帮助我！
这样的下界似乎有点不寻常，但我相信我们可以使用强归纳法给出 T(n) 的下界。我从一个有根据的猜测开始，即递归会将 O(lg n) 的一个因子添加到 Ω(n) 界限，并使用强归纳法来验证这个猜测。让我们考虑最小化 Ω(n) 以实现整个递归的下界的情况。也就是说，我们假设n隐藏在Omega符号中的函数实际上是Θ(n):
Assume true for all values of n up to k:
I.H. : T(n) < cn lg n - dn (for n < k)
Prove that it is true for k also:
T(k) = T(k/2) + T(k/4) + T(k/8) + Θ(n)
(IH) T(k) = (k/2)lg(k/2) + (k/4)lg(k/4) + (k/8)lg(k/8) - 3dn + Θ(n)
T(k) = ck lg k - 3dn + Θ(n)
< ck lg k - dn as required
因为我们可以选择足够大的常数 d 来超过隐藏在 Theta 符号中的常数。由于 cn lg n 是 Ω(n lg n)，我们可以将其作为递归的下界。由于原文中的 Ω(n) 项，我相信这是我们可以给出的最严格的渐近界限。