math - 证明 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 ₀，我们有 n！≤ c(n - 1)!。这意味着对于任何 n ≥ n ₀，我们都有 n! /（n - 1）！≤ c，或者说 n ≤ c。但是如果我们选择 n = max{n ₀ , c} + 1，那么我们知道 n ≥ n ₀并且 n ≥ c + 1，与 n ≤ c 相矛盾。由于我们有矛盾，假设一定是错误的，因此 n! ≠ O((n - 1)!)。

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

希望这可以帮助！