我有公式a(n)= n * a(n-1)+1; a(0)= 0
在没有主定理的情况下，如何从中获得Omega，Theta或O表示法？或者没有人有一个很好的网站来理解解释
最佳答案
大师定理甚至都不适用，因此不能使用它不是什么限制。
在这里可行的一种方法是猜测上下限，然后在猜测正确的情况下通过归纳证明这些猜测。
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) = 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)