函数的渐近比较

Question

我想逐渐比较以下函数，然后按升序排列它们。还要求提供适当的解释，方程式（lg（n）），SquareRoot（n！），SquareRootlg（n！），（lg（n））!,（SquareRoot（lg n））！，SquareRoot （lg n）！

Answer 1

如果您想知道“通用解决方案”，并且您可以按照很多步骤进行渐近函数比较。以下是我建议：

使用limit definition of BigO notation，一旦你知道了：

f(n) = O(g(n)) iff limit (n approaches +inf) f(n)/g(n) exists and is not +inf 

您可以使用Computer Algebra System，例如开源Maxima，这里是Maxima documentation about limits。

所以，检查lg(n)*lg(n) = O(sqrt(n))可卡犬被检查(lg(n)lg(n))/sqrt(n)限制：

(%i1) limit((log(n)^2)/(sqrt(n)), n, inf); 
(%o1)         0 

如果你喜欢，更长，更具描述性的符号：（！n）的

(%i1) f(n) := log(n)^2 ; 
              2 
(%o1)       f(n) := log (n) 
(%i2) g(n) := sqrt(n) ; 
(%o2)       g(n) := sqrt(n) 
(%i3) limit(f(n)/g(n), n, inf); 
(%o3)         0