为什么以下函数序列按渐近增长率排序？

Question

以增加Θ顺序排列以下表达式.如果两个函数具有相同的增长顺序,则应说明这一事实.

N日志N,N- ^-1,登录N,N- ^日志N,10N + N ^3/2,π ^ñ,2 ^ñ,2 ^{为log N},2 ^{2 为log N},登录N!

有人可以向我解释为什么以下答案是正确的吗？

n ^-1 «log n«2 ^{log n} «n log n = log n!«10N + N ^3/2 «Ñ ^{为log N} «2 ^Ñ = 2 ^{2 为log N} «π ^Ñ

Answer 1

你应该使用以下事实:

lim(n->?) f(n)/ g(n) = 0  this gives you ?(f(n)) < ?(g(n))
lim(n->?) f(n)/ g(n) = c; c > 0 this gives you ?(f(n)) = ?(g(n))
lim(n->?) f(n)/ g(n) = ?  this gives you ?(f(n)) > ?(g(n))

现在使用你得到:

lim(n->?) n^?1 / log n = lim(n->?) 1 / (n * log n) = 0.

这立即给你 ?(n^?1) < ?(log n)

继续下去.

对于某些计算,您可能会发现L'Hôpital的规则很有帮助.