math - 递归关系：求解 T(n-1) 的 BigO

Question

我正在为 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

T(n) = T(1)

所以结果是

T(n) = O(1)

我不完全确定这是否正确，但我不确定这是否如此简单。

Answer 1

只要你有一个基本案例，是的，这是正确的。

我假设复发被定义为

T(0) = k（对于某个常数 k），并且

T(n+1) = T(n)

然后你可以通过归纳证明所有自然数 n 的 T(n) = k。

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

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

希望这可以帮助！