解决：T(n) = T(n-1) + n

Question

解决：T(n) = T(n-1) + n

5

在Cormen的《算法导论》中，我正在尝试解决以下问题：证明递归关系T(n) = T(n-1) + n的解是O(n2)，使用代换法证明。但我似乎找不到正确的过程。教材只简单地涉及了它，而我搜索的大多数网站似乎都假定我已经知道了如何使用代换法。如果有人能给我一个简单的、分步的指南，或者甚至是一个链接，我会非常感激。为了方便起见，这是我迄今为止的尝试： T(n) <= c(n^2) <= c(n-1)^2 + n <= c(n^2 -2n +1) + n（我很确定这不小于c(n^2)）谢谢。更新:这里有一个例子，说明我想要实现的方法，以避免混淆。证明解是O(nlog(n)) T(n) = 2T([n/2]) + n 代换法要求我们证明对于某个正常数c>0，T(n) <= cn*lg(n)。假设对于任意小于n的正整数m=[n/2]，该界限成立，得到T([n/2]) <= c[n/2]*lg([n/2])。将其代入递归式得到以下结果： T(n) <= 2(c[n/2]*lg([n/2])) + n <= cn*lg(n/2) + n = cn*lg(n) - cn*lg(2) + n = cn*lg(n) - cn + n <= cn*lg(n)（只要c>=1，最后一步就成立）

- user2012892

作业标签已被弃用。 - Alexey Frunze

你能为这个添加归纳/替换标签吗？它来自于书中的“替换”部分。 - Brian Wiley

2个回答

10

请问这是一个纯数学问题吗？

从 T(n) = T(n-1) + n，我们得到：

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

将上述所有方程式相加得到：

T(n) - T(0) = 1 + 2 + ... + (n-1) + n = n * (n+1) / 2 = O(n ^ 2)

我们完成了。

更新（我不确定这是否符合原始问题中所要求的替换）：

T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-3) + (n-2) + (n-1) + n
= ... 
= T(1) + (2 + 3 + ... + n)
= T(0) + (1 + 2 + ... + n)
= T(0) +  n * (n+1) / 2
= O(n ^ 2)

- Hui Zheng

感谢您的回复，但我认为那是迭代，而不是替换。虽然在以后的问题中可能会派上用场，还是谢谢。 - user2012892

我更新了我的回答，这符合您的需求吗？ - Hui Zheng

我认为替换涉及将T(N)替换为c(n^2)，并使用它来证明关系。因此，上面是我徒劳的尝试。你的解决方案似乎涉及到书后面的一种方法，称为迭代或解决递归树。再次声明，我可能是错的。如果我知道我是对的，我就不会在这里了 :) - user2012892

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- thang · Accepted Answer

我猜这应该是归纳法？

因此，基本情况 n=1 很简单。归纳情况，假设 n>1。 (*) 假设T(n-1)是O((n-1)²)=O(n²)。证明T(n)也是O(n²)。

 T(n) = T(n-1) + n
      < c (n-1)^2 + n,  assume c>1 wlog
      < c n^2 - 2cn + c + n
      < c n^2 - (2c - 1)n + c
      < c n^2

当n > 1，c > 1时，以下是拆分:

首先注意当c > 1时，2c - 1 > c，因此您可以得到

      < c n^2 - (2c - 1)n + c
      < c n^2 - (c)n + c

接下来，注意当n > 1时，-(c)n+c = (1-n) c < 0，因此你会得到：

      < c n^2 - (c)n + c
      < c n^2

由于存在一个常量c，使得T(n) < c n^2，很明显T(n)是O(n²)。

这大概符合你想要的吗？我不得不多次编辑它以解决边缘情况。