解决复发的替代方法

Question

首先抱歉提出这样一个基本问题.

但是我很难理解用于解决复发的替代方法.我正在关注Algo.s-CLRS简介.由于我无法找到足够的例子和模糊性是主要关注点.尤其是归纳步骤.在教科书中我们必须证明f(n)意味着f(n + 1)但在CLRS中这一步骤缺失或可能是我没有得到这个例子.请逐步解释如何证明O(n ^ 2)是递归函数T(n)= T(n-1)+ n的解

它是我想要了解的替代方法的一般步骤.如果你能够对强大的数学归纳有所了解,并提供关于替代方法的材料的链接,这也会有所帮助.

Answer 1

在替换方法中,简单地替换T(k)by的任何出现T(k-1) + k,并迭代地进行.

T(n) = T(n-1) + n = 
= (T(n-2) + (n-1)) + n = 
= T(n-3) + (n-2) + (n-1) + n = 
= ...  =
= 1 + 2 + ... + n-1 +  n

从算术级数的总和,你可以得到T(n)O(n^2).

请注意,替换方法通常用于直观了解复杂性,正式证明它 - 您可能需要一个不同的工具 - 例如数学归纳法.

正式的证据将是这样的:

Claim: T(n) <= n^2
Base: T(1) = 1 <= 1^2
Hypothesis: the claim is true for each `k < n` for some `n`.
T(n) = T(n-1) + n <= (hypothesis) (n-1)^2 + n = n^2-2n + 1 < n^2 (for n > 1)