递归关系：寻找大O
我试图找到以下递归关系的大 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
我不确定这是否正确，而且我真的很感激一些关于如何导出的指导大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
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!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
是的，你是对的：
这个和是
Yes, you are correct:
and this sum is
你所拥有的并不正确，但你走在正确的轨道上。
你犯的错误是：
你不能直接从第一行转到第二行。
随着 k 的增加，右侧的项数也会增加。
要看到这一点，可以这样写：
如果将这些加起来会发生什么？
一旦你这样做了，你能看出 c=1 和 c=2 的答案是什么吗？你能从中找出最终答案的模式吗？
What you have is not correct, but you were on the right track.
The mistake you made:
You cannot just go from the first line to the second line.
As you increase k, the number of terms in the right hand side increases too.
To see that think of writing it this way:
What happens if you add these up?
Once you do that, can you see what the answer will be for c=1 and c=2? Can you figure out a pattern for the final answer from there?
与其从 n 开始向下工作，不如从 0 开始向上工作（我假设递归在 0 处终止，并且您忽略了该位）。当您开始注意到一个固定点（即在所有情况下重复相同的模式）时，您就有了一个很好的答案候选者。尝试证明答案，例如通过归纳法。
Instead of working you way down from n, how about start by working your way up from 0 (I assume the recursion terminates at 0 and you left that bit out). When you start noticing a fixed point (ie a pattern which repeats the same in all cases) you have a good candidate for an answer. Try proving the answer, e.g. through induction.
我首先观察到 n^c 当然受到 n 值的影响，但对于 n 与 n + 1 来说不会变得更复杂 - 是 c 决定了该特定术语的“运行时间”。鉴于此，您可以假设（至少我会）该术语具有恒定的运行时间，并确定对于给定的 n 递归将执行多少次，您将得到您的界限。
I would start by observing that n^c, whilst of course influenced by the value of n, is not going to be any more complex for n vs. n + 1 - it's c that determines the "runtime" of that particular term. Given that, you can assume (at least I would) that the term has constant runtime and determine how many times the recursion will execute for a given n and you'll get your bound.
要弄清楚这些，请填写几个术语并寻找模式：
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 表达模式，您就得到了答案。
To figure these out, fill out a couple of terms and look for the pattern:
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) = ...
Now express the pattern in terms of n and you have your answer.
这是：
O(nc+1)。
为了表明这是一个合理的界限，请注意当
c = 1时，这显然是 θ(n2)。
Here it is:
which is O(nc+1).
To show this is a reasonable bound, note that when
c = 1,which is clearly Θ(n2).