比较功能的增长

Question

我有以下内容：

1. n!
2. nlogn
3. 2^n
4. sqrt3(n) = n^1/3
5. n^3

我们知道为了比较两个函数我们需要 lim n->infinity f(n) / g(n) 但我们也知道指数 > 多项式 > 多对数。我们也从斯特林那里知道 n! = o(n^n) 和 n! =ω(n^2)

所以以上函数的正确顺序是：（从小到大）4 -> 2 -> 5-> 3 ->1。我对吗？我是否必须找到限制才能证明上述内容？我可以只考虑上述事实而不是寻找极限吗？

Answer 1

你的回答是正确的。至于你需要证明什么，那真的取决于上下文。如果这是一篇算法论文，你可以假设每个阅读你论文的人都知道这一点。如果这是 class，最好的答案是与讲师或助教核实。 :-)

希望对您有所帮助！