如何获得Omega(n)

Question

我有一个公式 a(n) = n * a(n-1) +1 ; a(0) = 0

我该如何从中得到Omega, Theta或O表示法，而不用主定理，或者有没有一个好的网站可以了解这个解释。

- FoldFence

---

你尝试过什么？也许你可以先写下Omega、Theta和大O的定义，然后你可能想写下这个序列中的一些值，以了解它的增长和行为-现在你有猜测了吗？ -当你做到了并且仍然有问题来证明你的猜测时，请回来。 ;) - Random Dev

我已经写下了所有n = 0...10的a(n)，并且我已经找到了这个公式，现在我应该写出Omega(n)，但是我不知道如何做，也没有找到一个好的解释来帮助我完成。 - FoldFence

你有猜测你的Omega（或者更好的是，对于你的a(n) = Omega(g(n))函数g(n)可能是什么吗？ - Random Dev

我的猜测是Omega(n)是Omega(n!)，因为该算法用于排列，最小值是n个元素的排列的正常数量，因此为n!。 - FoldFence

Answer 1

大师定理甚至都不适用，因此无法使用它并不是什么限制。

一种在这里起作用的方法是猜测上下界，如果猜测得当，则通过归纳证明这些猜测。

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

一个合理的猜测是，对于n>1，a(n) >= n!。这对于 n=1 是成立的。假设对于 n=k-1 也成立。

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

因此，如果对于n=k-1成立，那么对于n=k也成立，所以对于所有正整数n，a(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!)。

- Douglas Zare

---

我删除了我的回答，因为我在开始时搞错了一些心算，处理了错误的序列。正确的序列具有闭合形式sum(factorial(n)/factorial(k) for k in range(n)) - factorial(n) + 1。 - orlp

Answer 2

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

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

如果这是真的，那么所有的 O、Θ 和 Ω 都是 n!。我相信你可以使用归纳法证明上述不等式或者它的某个变形（虽然我还没有尝试过）。

- anatolyg

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!) 中。

- user1196549

---

你能解释一下为什么要将a(n)除以n!吗？你是刚刚将a(n)与Omega(n!)相除了吗？因为你的解决方案与我的教授相同，但我不知道为什么应该这样做。 - FoldFence

了解函数与n!的接近程度，这将帮助找到一个近似的闭合公式。 - user1196549

一旦你猜到正确的形式是c*n!，你可以询问c的值。如果你能够得到a(n)/n!的恒定上下界，那么你已经确定了a(n)是Theta(n)，但你可以希望得到确切的常数，这个答案提供了它。 - Douglas Zare