替代方法：为什么这种递归会改变不等式和等号，以及为什么归纳步骤使用较小的值作为下一个值
Substitution Method : Why this recurrence changes inequality & equality sign And Why inductive step used smaller values as a next value
我正在阅读 CLRS 书籍以了解使用替换方法解决递归问题并找到以下示例：
Recurrence, T(n) = 2T(n/2) + n
Guess Solution, T(n) = O(nlgn)
Proof that T(n) ≤ cnlgn
我的问题是：
Q1：为什么解方程在不等号和等号之间改变符号≤ , =？
Q2：我们知道在数学归纳中，归纳步长是下一个值，所以如果当前值为n那么下一个值应该是(n+ 1).But 为什么他们使用 n/2 作为下一个归纳步骤？
请帮我解释一下这些question.It会集会帮助我理解替换Method.Thanks
Q1：这两个等式只是重写上一行，因为 log(a/b) = log(a) - log(b) 和 log(2) = 1
Q2：对于归纳步骤，由于我们将T(n)写成T(n/2)的函数，所以一步直接是2-factor。如果递推公式为 T(n) = f(T(n-1))，您将得到带有 1 加法的经典归纳步骤。
另请注意，您在此证明中假设 T(1) 可以在常数时间内完成。
我正在阅读 CLRS 书籍以了解使用替换方法解决递归问题并找到以下示例：
Recurrence, T(n) = 2T(n/2) + n
Guess Solution, T(n) = O(nlgn)
Proof that T(n) ≤ cnlgn
我的问题是：
Q1：为什么解方程在不等号和等号之间改变符号≤ , =？
Q2：我们知道在数学归纳中，归纳步长是下一个值，所以如果当前值为n那么下一个值应该是(n+ 1).But 为什么他们使用 n/2 作为下一个归纳步骤？
请帮我解释一下这些question.It会集会帮助我理解替换Method.Thanks
Q1：这两个等式只是重写上一行，因为 log(a/b) = log(a) - log(b) 和 log(2) = 1
Q2：对于归纳步骤，由于我们将T(n)写成T(n/2)的函数，所以一步直接是2-factor。如果递推公式为 T(n) = f(T(n-1))，您将得到带有 1 加法的经典归纳步骤。
另请注意，您在此证明中假设 T(1) 可以在常数时间内完成。