1

我试图找到以下递归关系的大 O 界：

T(n) = T(n-1) + n^c, where c >= 1 is a constant

所以我决定通过使用迭代来解决这个问题：

T(n) = T(n-1) + n^c
T(n-1) = T(n-2) + (n-1)^c
T(n) = T(n-2) + n^c + (n-1)^c
T(n-2) = T(n-3) + (n-2)^c
T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c
T(n) = T(n-k) + n^c + (n-1)^c + .... + (n-k+1)^c

Suppose k = n-1, then:

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

但是，我不确定这是否正确，另外，我非常感谢有关如何从中派生 Big O 的一些指导。非常感谢！

4

6 回答 6

3

是的，你是对的：

T(n) = n c + (n-1) c + (n-2) c + … + 3 c + 2 c + 1,

这个总和是

T(n) = O(n c+1 )。参见例如Faulhaber 的公式。事实上，您甚至可以确定前导项中的常数（即使它与算法的渐近性无关）：总和为 n c+1 /(c+1) + O( c )，您可以通过例如，使用，比如说，整合。

于 2010-07-13T03:23:34.053 回答
2

你所拥有的是不正确的，但你在正确的轨道上。

你犯的错误：

T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c    
T(n) = T(n-k) + n^c + (n-1)^c + (n-k+1)^c

你不能只从第一行到第二行。

随着 k 的增加，右侧的项数也会增加。

看到这样想这样写：

T(n) - T(n-1)  = n^c.

T(n-1) - T(n-2) = (n-1)^c
..

T(n-k) - T(n-k-1) = (n-k)^c.

..
T(2) - T(1) = 2^c

如果你把这些加起来会发生什么？

一旦你这样做了，你能看到 c=1 和 c=2 的答案是什么吗？你能从那里找出最终答案的模式吗？

于 2010-07-11T23:47:50.447 回答
0

与其从 n 开始向下工作，不如从 0 开始向上工作（我假设递归在 0 处终止，而你忽略了这一点）。当您开始注意到一个固定点（即在所有情况下都重复相同的模式）时，您就有了一个很好的答案候选者。尝试证明答案，例如通过归纳法。

于 2010-07-11T23:47:01.110 回答
0

我会首先观察 n^c，虽然当然会受到 n 值的影响，但对于 n 与 n + 1 来说，它不会变得更复杂 - 它是 c 决定了该特定术语的“运行时间”。鉴于此，您可以假设（至少我会）该术语具有恒定的运行时间，并确定对于给定的 n 递归将执行多少次，您将得到您的界限。

于 2010-07-11T23:50:07.803 回答
0

要弄清楚这些，请填写几个术语并寻找模式：

T(1) = 0 + 1^c

T(2) = T(1) + 2^c = 0 + 1^c + 2^c

T(3) = T(2) + 3^c = 0 + 1^c + 2^c + 3^c

T(4) = ...

现在用 n 来表达模式，你就有了答案。

于 2010-07-13T03:03:51.990 回答
0

这里是：

T(n) = n^c + (n-1)^c + (n-2)^c + ... + 2^c + 1^c
     < n^c +     n^c +     n^c + ... + n^c + n^c
     = n * n^c
     = n^(c+1)

这是 O(n c+1 )。

为了证明这是一个合理的界限，请注意，当c = 1，

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

这显然是 Θ(n 2 )。

于 2010-07-13T03:38:48.777 回答