1

使用 C++ 中的 Robert Sedwick 书籍自行阅读算法

一个递归函数，它将大小为 N 的问题分成两个独立的（非空）部分，它递归地解决这些部分，调用自身的次数少于 N 次。

如果这些部分是大小为 k 的部分之一和大小为 Nk 的部分，那么我们使用的递归调用的总数是 T(n) = T(k) + T(nk) + 1，对于 N>=1 和 T( 1) = 0。

解 T(N) = N-1 是直接归纳法。如果大小总和小于 N，则调用次数小于 N-1 的证明来自相同的归纳论证。

我对上述文字的问题是

  1. 作者如何通过归纳得出解决方案 T(N) = N-1？请帮我理解。
  2. 作者的意思是“如果大小总和小于 N，则调用次数小于 N-1 的证明来自相同的归纳论证”？

我是数学归纳法的新手，所以很难理解。

感谢您的时间和帮助

4

3 回答 3

2

(1) 通过归纳：

T(1) = 0 (base)
T(N) = T(k) + T(N-k) + 1 (definition of problem)

我们假设对于每个n < N，我们得到T(n) = n-1
因为两者k和N-k都更小N，所以我们从归纳假设中得到：

T(N) = (k-1) + (N-k-1) + 1 = N-1
         ^        ^
        T(k)    T(N-k)

(2) 使用相同的论点：如果

T(N) = T(k) + T(m) + 1 where k+m < N

那么同样的证明将导致T(N) < N-1

于 2012-09-04T13:54:21.490 回答
0

对于您问题的第一部分，首先我应该提到我认为作者是错误的，因为您有这个递归方程：

T(n) = T(k) + T(nk) + 2 ：因为对于 n > 1，您称两个较小的部分不是一个。现在我们的假设是 2(n-1) 次递归调用。

现在让我们用归纳法检查它：

T(1) -> no recursive call.
T(2) = T(1) + T(1) + 2 : two recursive call.
...
T(n) = T(k) + T(n-k) + 2 = 2(k-1) + 2(n-k-1) + 2 = 2n-2 = 2(n-1).

同样对于你问题的第二部分，作者的意思是如果你分成两部分，使得部分的总和小于 n，就像大小为 k 的部分和另一部分大小为 n-2k 的 k > 1。

于 2012-09-04T14:02:18.960 回答
0

首先，我们不是“通过归纳得出解”，我们用归纳来证明我们最初的猜测。现在，为了猜测，我们可以使用递归树之类的方法。
在您的问题中，最坏的情况是 for k=1，因为它会导致最多的递归。我们还知道每个级别的成本：

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

现在我们必须找到成本T(n-1)并将其添加到成本T(n)=1中。
我们猜测最终的结果是N-1。在这一步中，我们使用归纳法来证明我们的猜测。

更新：
T(n) 的成本为 1 （ T(1) 为零，加上将计算的 T(n-1) ，加上 1 => 1 ）， T(n-1) 的成本也是一（与同样的逻辑）。我们往下走 n-1 的深度。最后一个是 T(1)，它是零。（画一棵树，它会帮助你理解）。
这种猜测生长顺序的方法称为递归树。现在你可以通过归纳来证明它。

有关如何应用归纳来证明假设的更多信息，请参阅CLRS等教科书。

于 2012-09-04T14:15:21.993 回答