algorithm - 替换方法 : Why this recurrence changes inequality & equality sign And Why inductive step used smaller values as a next value

Question

我正在阅读 CLRS 书籍以了解使用替换方法解决递归问题并找到以下示例:

   Recurrence, T(n) = 2T(n/2) + n
   Guess Solution, T(n) = O(nlgn)
   Proof that T(n) ≤ cnlgn

我的问题是:

Q1:为什么解方程在不等号和等号≤ , = 之间改变符号？

Q2:我们知道在数学归纳法中，归纳步是下一个值，所以如果当前值为n那么下一个值应该是(n+1)。但是为什么他们使用 n/2 作为下一个归纳步骤？

请帮我解释一下这些问题。它会帮助我理解替代方法。谢谢

Answer 1

Q1 : 这两个等式只是对上一行的重写，因为 log(a/b) = log(a) - log(b) 和 log(2) = 1

Q2:对于归纳步​​骤，由于我们将 T(n) 写入 T(n/2) 的函数中，因此一步直接是一个 2 因子。如果递推公式为 T(n) = f(T(n-1))，您将拥有带 1 加法的经典归纳步骤。

另请注意，您在此证明中假设 T(1) 可以在常数时间内完成。