算法导论第三版-习题2.3 -3-nlg(n)的归纳证明
Introduction to Algorithms Third Edition - Exercise 2.3 -3 - Inductive proof of nlg(n)
我正在阅读算法导论，第三版。在一个练习中，我们被要求使用归纳推理来证明
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? 它不符合我所知道的数学约定。
开始学习一些基础数学：
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.
的表达式
我正在阅读算法导论，第三版。在一个练习中，我们被要求使用归纳推理来证明
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? 它不符合我所知道的数学约定。
开始学习一些基础数学：
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.
的表达式