2

我正在阅读《算法导论》这本书，第三版。在一个练习中，我们被要求使用归纳推理来证明

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

其中 lg 是 log base 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?？它不符合我所知道的数学约定。

4

1 回答 1

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 的表达式。

于 2015-07-07T04:40:16.400 回答