证明f(n)总是O(f(n-1))

Question

假设当n变为无穷大时f(n)变为无穷大.

这是一个家庭作业问题,我希望得到一个想法/指导,而不是完整的答案.

Answer 1

事实并非如此.考虑函数f(n)= n!作为一个反例,当n进入无穷大时,肯定会走向无限.但是,我们可以证明,n!≠O((n - 1)!).

证据是矛盾的.假设n!= O((n - 1)!).那么存在某个n ₀和c,使得对任意n≥ñ ₀,我们有N!≤c(n - 1)!这意味着,对任意n≥ñ ₀,我们有N!/(n - 1)!≤c,或n≤c.但是,如果我们挑选N =最大{N ₀,C} + 1,那么我们就知道是n≥Ñ ₀和使得n≥C + 1,矛盾是n≤℃.既然我们有矛盾,那么假设必定是错误的,因此n!≠O((n - 1)!).

如果你想知道我是怎么想到这个的:我的想法是找到一个增长如此迅速的函数,无论你选择什么常数,f(n + 1)和f(n)之间的比率最终都会如此很大,它会超过这个常数.恰好是n的情况!适合账单.回想起来,我应该记得那个!≠O((n - 1)!)因为许多算法都有像O((n + 1)!)这样的运行时,它不会简化为O(n!).

希望这可以帮助!