函數的漸近比較

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