算法 T(n) = T(n-1)+2

Question

如何在这个等式上应用主定理？

如果 T(1) = 1 且

T(n) = T(n-1)+2

这样一个程序的运行时间是多少？ T(1) = 1 有什么用？这是哪种情况，为什么？请详细解释。谢谢。

Answer 1

你不能在这里使用 Master Theorem（至少没有变量替换），因为它的格式不正确。

但是您的函数很容易分析并且在 Theta(n).

中

归纳证明，每个 k<n

T(k) <= 2k

T(n) = T(n-1) + 2 <= 2(n-1) + 2 = 2n -2 + 2 <= 2n
                   ^
               induction 
               hypothesis

归纳基础是 T(1) = 1 <= 2

以上显示 T(n) 在 O(n) 中，因为我们发现 c=2 使得 n>0，以下是正确的：T(n) <= c*n，这是 definition of big O notation.

类似地证明T(n)在Omega(n)中很容易，由此你可以得出结论T(n)在Theta(n)

中

Answer 2

感谢您的帮助。因此，在您的回答和一个新的递归方程的帮助下，我想我终于理解了。假设我有 T(N) = 1*T(n-1) + n^2。 Master Theorem 在这里也不适用，所以我有我的基本情况。

T(1) = 1
T(2) = 5
T(3) = 14
T(4) = 30

--> Proof by induction, T(k) <= 2k for each k<n

T(n) = T(n-1) + n^2 <= n^2(n-1) + n^2 = n^3 - n^2 + n^2 = n^3
                    ^
                induction 
                hypothesis
So this leads to O(N^3) ? not sure about this. Why not Omega or Theta.

我的 hypothesis/induction 什么时候会是 <、> 或 >=。

算法 T(n) = T(n-1)+2

Algorithmic T(n) = T(n-1)+2

algorithm

runtime

time-complexity