算法第三版简介-练习2.3 -3 - nlg(n)的归纳证明

Question

我正在读“算法导论”，第三版。在一个练习中，我们被要求用归纳推理来证明。

T(n) = {2 if n = 2, 2T(n/2) + n if n > 2^k for k > 1} = nlgn

其中lg是log基2。本书提供了以下解决方案：

Base Case:
n = 2, T(2) = 2, 2lg(2) = 2

Assumption:
T (n/2) = (n/2)lg(n/2)

Induction:
T (n) = 2T (n/2) + n
= 2(n/2)lg(n/2) + n
= n(lg n − 1) + n
= n lg n − n + n
= n lg n

有人能解释为什么在假设步骤中使用n/2值吗？根据我对归纳的理解，我会使用值2^n，然后将其增加到2^(n+1)，以涵盖2的所有可能的幂。我想知道为什么我错了。此外，有人能解释一下改变2(n/2)lg(n/2)+n into n(lg n-1) + n?的操作吗?它不遵守我所知道的数学惯例。

Answer 1

开始学习一些基本数学：

lg(a/b) = lg(a) - lg(b)

这就是为什么：

2(n/2)lg(n/2)+n = n( lg(n) - lg(2)) +n= n( lg(n) - 1) + n

关于n/2的假设，这个假设是最好的假设，因为它简化了归纳步骤。在归纳步骤中，我们得到的结果很容易，没有任何严格的数学解释。

“Cormen”一书被认为是算法的圣经，它将这种求解递归的替代方法称为，其中我们首先假定递归对于给定的输入是真的，并使用该假设来判断我们的假设是否适合输入n的表达式。