asymptotic-complexity - 関数の漸近比較

Question

以下の関数を漸近的に比較し、昇順で並べていきたいです。また、適切な説明lg（（√n）！）、lg（SquareRoot（n！））、SquareRootlg（n！）、（lg（√n））!,（SquareRoot（lg n））!, SquareRoot（ lg n）！

Answer 1

「一般的な解決策」について疑問に思い、漸近関数の比較に多くのことをたどる場合。これが私がお勧めするものです：

知ったら、BigO表記の制限定義を使用します。

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

数式処理システム（たとえば、オープンソースのMaxima ）を使用できます。これは、Maximaのドキュメントにあります。

だから、チェックlg(n)*lg(n) = O(sqrt(n))はデーンになることができます：のチェック制限です(lg(n)lg(n))/sqrt(n)：

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

必要に応じて、より長く、より説明的な表記法：

(%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