递归关系:寻找大 O

问题描述

我试图找到以下递推关系的大 O 界:

I am trying to find the big O bound for the following recurrence relation:

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

所以我决定使用迭代来解决这个问题:

So I've decided to solve this by using iteration:

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 的一些指导.非常感谢！

I'm not sure if this is correct however, plus I would really appreciate some guidance as to how to derive Big O from this. Thanks a lot!

推荐答案

是的，你说得对:

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

这个总和是

T(n) = O(n).见例如Faulhaber 公式.事实上，您甚至可以确定前导项中的常数(即使它与算法的渐近性没有密切关系):总和为 n/(c+1) + O()，您可以通过例如使用集成来确定.

这篇关于递归关系:寻找大 O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！