algorithm - 如何获得 Omega(n)

Question

我有公式 a(n) = n * a(n-1) +1 ； a(0) = 0

如果没有主定理，我如何从中得到 Omega、Theta 或 O 符号，或者有没有人有一个很好的网站来理解解释

Answer 1

Master 定理甚至不适用，因此不能使用它也不是什么限制。

这里可行的方法是猜测上限和下限，如果猜测正确，则通过归纳法证明这些猜测。

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 10
a(4) = 41

下界的合理猜测是 a(n) >= n!对于 n>1。这对于 n=1 是正确的。假设 n=k-1 为真。

a(k) = ka(k-1)+1 
     >= k (k-1)! + 1 
     >= k!. 

所以，如果 n=k-1 成立，那么 n=k 成立，所以 a(n) >= n!对于所有正整数 n，并且 a(n) = Omega(n!)。

上限的合理猜测是 a(n) <= 2(n!)。这对于前几个值是正确的，但事实证明使用归纳法证明有点尴尬。有时使用归纳证明，最好证明一些更强大的东西。在这种情况下，最好证明 a(n) < 2(n!)，或者 a(n)<=2(n!)-1。这对于 n=1 是正确的。假设对于某些 k-1>=1，n=k-1 成立。然后

a(k) = k(a(k-1))+1 
    <= k(2(k-1)!-1)+1 
     = 2(k!) +1-k 
    <= 2(k-1)!-1. 

因此，对于任何 n>=1，a(n) < 2(n!)。由于我们有一个下界和一个上界，形式为 c*(n!)，a(n) = Theta(n!)。