按增长率排列下列函数

Question

我怎样才能按增长率排序下列功能？n^(logn)，3^n，(logn)^n，n选择n-4，n^3？

我有的是: n^3，n选择n-4，n^logn，3^n，(logn)^n，但我不确定这是否正确。

Answer 1

你点的菜在我看来是对的。

1. n^3显然是列表中最小的多项式。
2. n choose (n-4)为n! / ((n-4)! 4!) = n (n-1) (n-2) (n-3) / 4!。它是O(n^4)，是第二个最小的函数。
3. n^log n = exp((log n)^2)不是偶数指数，它是拟多项式.
4. 3^n是经典指数。
5. (log n)^n的增长明显快于3^n，因为随着n的增长，它的基础和功率都在增加。顺便说一句，它仍然是指数式的，因为例如(log n)^n = exp(n log log n) = O(exp(n^2))。