我如何找到这个递归的渐近紧界？T(n) = T(n-2) + (n/2)

Question

T(n-2)部分让我有点困惑，因为如果我找到T(n-2)并将其替换为T(n) = T(n-2) + into (n/2)，对于这一部分，k=2还是3？

另外，T(n-1)会发生什么？

我是不是不承认它，或者我应该如何应用它来解决这个递归？

我该如何处理这个递归并解决它？(我使用替换方法接近它，但不确定如何解决它)

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

Answer 1

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

甚至可以考虑n，然后考虑k=n/2的T(n) = T(2k)。让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

现在我们知道在sum 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，证明同样的成立是相似的。