如何获得 Omega(n)

Question

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

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

Answer 1

您已经注意到您的公式非常接近阶乘 n!。现在你可以用更正式的方式表达这个发现：你可以证明，例如，

n! < a(n) < 2*n! (for big enough n)

如果这是真的，那么O、Θ和Ω都是n!。

我相信你可以使用归纳法证明上面的不等式，或者它的一些变体（虽然没试过）。

Answer 2

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!).

Answer 3

提示：

a(n) 除以 n!，第一项是

a(1)/1! = 1/1! = 1
a(2)/2! = (2.1+1)/2! = 1 + 1/2!
a(3)/3! = (3.(2.1+1)+1)/3! = 1 + 1/2! + 1/3!
a(4)/4! = (4.(3.(2.1+1)+1)+1)/4!= 1 + 1/2! + 1/3! + 1/4!
...

这建立了紧密包围

n! <= a(n) < (e-1).n!

和 a(n) 在 Θ(n!).

如何获得 Omega(n)

How to get Omega(n)

algorithm

big-o

complexity-theory

big-theta