5

在 Cormen's Introduction to Algorithm 的书中，我试图解决以下问题：

证明递归关系 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
代入法要求我们证明 T(n) <= cn*lg(n) 可供选择常数 c > 0。假设这个界限适用于所有正数 m < 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 最后一步就成立

我可以遵循这个逻辑很好，但是当我尝试复制上述问题中的步骤时，我被卡住了。

4

2 回答 2

13

我想这应该是感应？

所以基本情况 n=1 是微不足道的。归纳案例，假设 n>1。(*) 假设 T(n-1) 为 O((n-1) 2 )=O(n 2 )。证明 T(n) 也是 O(n 2 )。

 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) < cn^2，显然 T(n) 是 O(n 2 )。

这大致符合你想要的吗？不得不对其进行多次编辑以修复边缘情况。

于 2013-01-28T22:03:13.400 回答
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)

我们完成了。

更新（我不确定这是否被称为 OP 所需的替换）：

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)
于 2013-01-26T03:00:37.280 回答