1

我尝试确定递归关系给出的运行时间，但我的结果不正确。

复发

T(n) = c + T(n-1) if n >= 1
     = d          if n = 0

我的尝试

我构建了这个递归树：

                   n
                   |
                  n-1
                   |
                  n-2
                   |
                  n-3
                   |
                  n-4
                   |
                  n-5
                   |
                   |
                   |
                   |
                   |
                   |
                Till we get 1

现在在 level i，子问题的大小应该是，n-i

但最后我们想要一个大小为 1 的问题。因此，在最后一级， n-i=1它给出了i=n-1.

所以树的深度变成n-1了，高度变成了n-1+1= n。

现在解决此递归所需的时间=树的高度*每个级别所需的时间，即：

n+(n-1)+(n-2)+(n-3)+(n-4)+(n-5)+ ...
==> (n+n+n+n+n+ ... )-(1+2+3+4+5+ ... )
==> n - (n(n+1)/2)

现在所花费的时间 = n* ((n-n2)/2) 应该给出的顺序是 n 2，但这不是正确的答案。

4

3 回答 3

3

现在在第 i 层，子问题的大小应该是，ni

对，那是正确的。但是您假设运行时间等于所有子问题大小的总和。试想一下，已经将前两个级别相加了n + (n - 1) = 2n - 1，为什么问题大小会增加？免责声明：有点手忙脚乱，并不完全准确。

公式实际上说的是什么

T(n) = c + T(n-1)

公式说，解决一些问题n所花费的时间与解决问题大小所花费的时间相同，但问题大小加上一个额外的常数c：c + T(n - 1)

上述陈述的另一种表达方式是：鉴于问题需要一些时间t才能达到一定的问题规模，因此需要一定t + c的问题规模，即大一倍。

我们知道，在问题大小为 时n = 0，这需要时间d。根据第二个说法，对于一个更大的尺寸，n = 1将需要d + c。再次应用我们的规则，因此d + c + c需要n = 2. 我们得出结论，d + n*c任何n.

这不是证据。要实际证明这一点，您必须使用 amit 所示的归纳法。

正确的递归树

您的递归树仅列出问题大小。恐怕这没什么用。相反，您需要列出上述问题大小的运行时。

树中的每个节点都对应一个特定的问题大小。您写入该节点的内容是问题大小所需的额外时间。即，您将节点的所有后代加上节点本身求和以获得特定问题大小的运行时。

这种树的图形表示如下所示

Tree        Corresponding problem size
c                                    n
|
c                                    n - 1
|
c                                    n - 2
|
c                                    n - 3
.
.
.
|
c                                    2
|
c                                    1
|
d                                    0

形式化：如前所述，节点的标签是解决该问题大小所需的额外运行时间，加上它的所有后代。最上面的节点代表一个问题大小n，带有标签c，因为它是除 之外的T(n-1)，它使用 连接到它|。

在一个公式中，你只会写这个关系：T(n) = c + T(n-1)。鉴于这棵树，您可以看到这如何适用于每个n>=1. 你可以这样写：

T(n)     = c + T(n - 1) # This means, `c` plus the previous level
T(n - 1) = c + T(n - 2) # i.e. add the runtime of this one to the one above^
T(n - 2) = c + T(n - 3)
...
T(n - (n - 2)) = c + T(1)
T(n - (n - 1)) = c + T(0)
T(0) = d

您现在可以从下到上展开条款：

T(n - (n - 1)) = c + T(0)
T(0) = d

T(n - (n - 2)) = c + T(1)
T(n - (n - 1)) = c + d
T(0) = d

T(n - (n - 3)) = c + T(2)
T(n - (n - 2)) = c + (c + d)
T(n - (n - 1)) = c + d
T(0) = d

T(n - (n - 4)) = c + T(3)
T(n - (n - 3)) = c + (2*c + d)
T(n - (n - 2)) = c + (c + d)

...

T(n) = c + T(n - 1)
T(n - 1) = c + ((n-2)c + d)

T(n) = c + (n-1)c + d = n*c + d
T(n - 1) = (n-1)c + d

求和1 to n

n+(n-1)+(n-2)+(n-3)+(n-4)+(n-5)+ ...
==> (n+n+n+n+n+ ... )-(1+2+3+4+5+ ... )
==> n - (n(n+1)/2)

从第一行到第二行，您已将问题从 summing 减少1 to n到 summing 1 to n-1。这不是很有帮助，因为您遇到了同样的问题。

我不确定你在第三行做了什么，但你从第一行到第二行的过渡基本上是正确的。

这将是正确的公式：

高斯技巧将 1 与 n 相加

于 2012-10-07T12:12:45.020 回答
2 
T(n) = c + T(n-1) 
     = c + (c + T(n-2)) 
     = ... 
     = c*i + T(n-i) 
     = ...
     = c*n + T(0)
     = c*n + d

如果我们假设 c,d 是常数 - 它会让你O(n)

为了证明它在数学上 - 可以使用数学归纳法

对于每个k < n假设T(n) = c*n + d
Base 是T(0) = 0*n + d = d，这对于 n < 1 是正确的

T(n) = c + T(n-1)               (*)
     = c + (n-1)*c + d 
     = c*n + d

(*) 是归纳假设，并且是有效的，因为 n-1 < n

于 2012-10-07T10:31:44.713 回答
1

复杂度为 O(n)。

正如您所描述的，这些函数通过使用常量操作“c”将输入 n 的问题转换为 (n-1) 的问题。

因此，向下移动递归树，我们将总共有 n 个级别，并且在每一步我们都需要一些恒定的操作“c”。

因此将有总共 c*n 次操作导致复杂度 O(n)。

于 2012-10-07T11:51:23.247 回答