递归关系：寻找大O

Question

我试图找到以下递归关系的大 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 的指导。多谢！

Answer 1

是的，您是正确的：

t（n）= n ^{c +（n-1） c +（n-2） c + ... + 3 c + 2 c + 1，}

并且此总和是

t（n）= o（n ^{c + 1 ）。见e.g. faulhaber's formure 。实际上，您甚至可以确定领先术语中的常数（即使它不是算法的渐近学的杰出）：总和是n c + 1 /（c + 1）+ o（ c ），正如您可以通过例如使用，例如，使用，定义集成。}

Answer 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

.

如果添加这些up，会发生什么？

一旦你这样做，你能看到答案是c= 1和c= 2的答案吗？你能从那里弄清楚最终答案的模式吗？

Answer 3

而不是从n从n下来工作，从0开始，从0开始，从0开始，当您开始注意到一个固定点（即，在所有情况下重复的模式）时，您可以获得答案的好候选者。尝试证明答案，例如答案。通过诱导。

Answer 4

我首先观察n ^ c，而当然是由n值的影响，对于n + n + 1，它不会更复杂 - 它是确定该特定的“运行时”的c学期。鉴于此，您可以假设（至少我将）该术语具有持续的运行时，并确定递归递归的次数为给定的n且您将获得绑定。

Answer 5

要解决这些问题，请填写几个术语并查找模式：

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表示模式，你有答案。

Answer 6

这里是：

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²).