递归关系:求解T(n-1)的BigO [英] Recurrence Relation: Solving BigO of T(n-1)

问题描述

我正在解决Big O的一些递归关系问题.

I'm solving some recurrence relation problems for Big O.

T(n) = T(n-1)

我从开始:

T(n)   = T(n-1)
T(n-1) = T(n-2)
..
T(n) = T(n-k)

现在将k设置为n-1

Now setting k to n-1

T(n) = T(1)

所以结果是

T(n) = O(1)

我不确定这是否正确，但是我不确定这很容易.

I'm not entirely sure if this is correct, but I'm uncertain that this is so easy.

推荐答案

只要您有基本情况，是的，这是正确的.

As long as you have a base case, yes, that's correct.

我假设复发定义为

T(0)= k(对于某些常数k)，并且

T(0) = k (for some constant k), and

T(n + 1)= T(n)

T(n+1) = T(n)

那么您可以通过归纳证明对于所有自然数n，T(n)= k.

Then you can prove by induction that T(n) = k for all natural numbers n.

• 基本情况:如果n = 0，则根据需要T(n)= T(0)= k.
• 归纳步骤:假定T(n)= k.然后，根据需要，T(n + 1)= T(n)= k.

• Base case: If n = 0, then T(n) = T(0) = k, as required.
• Inductive step: Assume T(n) = k. Then T(n + 1) = T(n) = k, as required.

因此，T(n)= k = O(1).

Therefore, T(n) = k = O(1).

希望这会有所帮助！

这篇关于递归关系:求解T(n-1)的BigO的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！