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