我如何找到这种递归的渐近紧束缚？ T(n) = T(n-2) + n log (n/2)

Question

T(n-2) 部分让我有点困惑，因为如果我找到 T(n-2) 并将其代入 T(n) = T(n-2) + n log(n/2), 对于这部分，k = 2 还是 3?

此外，T(n-1) 会怎样？

我只是不承认它还是我应该如何应用它来解决这种复发？

我将如何处理和解决这种复发？（我是用代入法解决的，但不知道怎么解决）

T(n) = T(n-2) + nlog(n/2)

Answer 1

递归关系的解由两个独立的部分组成，偶数项和奇数项。您需要两个初始值，一个用于 T_0，一个用于 T_1.

考虑n偶数，然后T(n) = T(2k)为k=n/2。让F(k) = T(2k)。我们的等式变成

F(k) = F(k-1) + 2 k log(k)
     = 2 k log(k) + 2 (k-1) log(k-1) + .. 2 1 log(1) + T_0
     = 2 sum i log(i) + T_0

现在我们知道总和log(i) < log(k)内，所以我们得到

F(k) < 2 log(k) sum i + T_0
     = 2 log(k) k * (k+1) / 2 + T0
     = log(k) k * (k+1) + T_0
     = O(k^2 log(k))

所以，对于偶数 n:

T(n) = O(n^2 log(n))

证明同样成立的奇数 n 是相似的。

How do I find the asymptotic tight bound to this recurrence? T(n) = T(n-2) + n log (n/2)