如何获得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!).

对上限的合理猜测是在(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!).