algorithm - 我怎样才能解决这个递归关系

Question

我有一个递归关系:

我把它变成了

我如何证明 T(n) 属于 BigOmega(2^n)

Answer 1

所以让我们看看 T(n) = 2 * T(n - 1) + T(n/2) + 1/2。
让我们将其与去除较小项的递推关系进行比较:
S(n) = 2 * T(n - 1)
我们显然可以看到
T(n) = Ω(S(n))
所以只需要证明 S(n) = Ω(2n)。
让我们展开 S(n):
S(n) = 2 * T(n - 1)
= 2 * 2 * T(n - 2)
= 2 * 2 * 2 * T(n - 3)
我们注意到我们得到 2 * 2 * ... * 2 = 2n。
因此，S(n) = Ω(2n)，因此 T(n) = Ω(S(n)) = Ω(2n)。 □