-2

假设当 n 趋于无穷时 f(n) 趋于无穷。

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

4

1 回答 1

5

这不是真的。考虑函数 f(n) = n! 作为一个反例,当 n 趋于无穷时,它肯定趋于无穷。但是,我们可以证明 n! ≠ O((n - 1)!)。

证明是矛盾的。假设 n! = O((n - 1)!)。那么存在一些 n 0和 c 使得对于任何 n ≥ n 0,我们有 n!≤ c(n - 1)!。这意味着对于任何 n ≥ n 0,我们都有 n! /(n - 1)!≤ c,或者说 n ≤ c。但是如果我们选择 n = max{n 0 , c} + 1,那么我们知道 n ≥ n 0并且 n ≥ c + 1,与 n ≤ c 相矛盾。由于我们有矛盾,假设一定是错误的,因此 n! ≠ O((n - 1)!)。

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

希望这可以帮助!

于 2013-10-01T23:36:23.037 回答