algorithm - 求解递归的替代方法

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)