求解递归问题的代换法
求解递归问题的代换法
提问于 2013-01-09 16:00:16
首先，很抱歉问了这么基本的问题。
但我在理解解决递归问题的替换方法时遇到了困难。下面是Algo.s -CLRS的介绍。因为我找不到足够的例子，歧义是主要的concern.Especially，归纳和教科书，我们必须证明f(n)蕴含f(n+1)，但是在CLRS中，这一步丢失了，或者可能是我没有得到例子。请逐步说明如何证明O(n^2)是递归函数T(n)=T(n-1)+n的解
我想要理解的是代换方法的一般步骤。如果你能对强大的数学归纳法有所了解，并提供有关替换方法的材料的链接，这也会很有帮助。
回答 1
Stack Overflow用户
发布于 2013-01-09 16:01:46
在替换方法中，简单地用T(k-1) + k替换任何出现的T(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从sum of arithmetic progression中，您可以得到T(n)在O(n^2)中。
请注意，替换方法通常用于直观地了解复杂性是什么，为了正式证明这一点-您可能需要一个不同的工具-例如mathematical induction。
正式的证明是这样的：
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)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14230639
复制相关文章
相似问题
腾讯云开发者
