安排他们的大哦，复杂性增加的顺序 [英] Arrange in increasing order of their Big Oh Complexity

问题描述

因此​​，如果给定

4N ^ 2，log3中（N），20N，N ^ 2.5的log（n！），N ^ N，3 ^ N，N-的log（n），100N ^（2/3），2 ^ N， 2 ^（N + 1）中，n！，第（n-1）！2 ^ 2n个

4n^2, log3(n), 20n, n^2.5, log(n!), n^n, 3^n, n log (n), 100n^(2/3), 2^n, 2^(n+1), n!, (n-1)!, 2^2n

订单（为了增加自己的大O的复杂性），将

The order (increasing order of their big O complexity) would be

log3中（N）其中​​， 20N＆LT; ñLOGN＆LT; 4N ^ 2版; 100N ^（2/3）＆其中;的log（n！）＆LT; ñ^（2.5）＆LT; 2 ^ N＆LT; 2 ^（N + 1） - ; 3 ^ N＆LT; 2 ^（2n）的＆其中;第（n-1）！ ＆LT; ñ^ N＆LT; N！

log3(n) < 20n < n logn < 4n^2 < 100n^(2/3) < log(n!) < n^(2.5) < 2^n < 2^(n+1) < 3^n < 2^(2n) < (n-1)! < n^n < n!

这是当n是一个庞大的数字。是吗？

this is when n is a large number. Is that right?

推荐答案

综上所述，当n趋于正无穷，在大哦复杂性方面：

To sum up, as n tends to +infinite, in terms of big Oh complexity:

log3中（N）其中​​， 100N ^（2/3）＆其中; 20N＆LT;的log（n！）＆LT;的n log（n）的＆LT; 4N ^ 2版; ñ^（2.5）＆LT; 2 ^ N〜2 ^（N + 1） - ; 3 ^ N＆LT; 2 ^（2n）的＆其中;第（n-1）！ ＆LT; N！ ＆LT; ñ^ N

log3(n) < 100n^(2/3) < 20n < log(n!) < n log(n) < 4n^2 < n^(2.5) < 2^n ~ 2^(n+1) < 3^n < 2^(2n) < (n-1)! < n! < n^n

这维基百科页面可能会感兴趣。

编辑：关于N！对ñ^ N

regarding n! vs. n^n

使用斯特灵公式，我们有：

因此，O（！n）的〜O（开方（N）* N ^ N * E ^（ - N））
因此，O（开方（N））〜O（E ^（ - N））当且仅当为O（n ^ n）的〜O（N！）
。 但是，O（开方（N））〜O（E ^（ - N））是假的
。 因此为O（n ^ n）的〜O（N！）是假的。
由于N！ ＆LT; ñ^ N，我们有N！ = O（N ^ N）。 QED。


下面是一个证明 djfm 它不依赖于斯特灵公式：

Using Stirling's approximation, we have:

therefore O(n!) ~O(sqrt(n) * n^n * e^(-n))
hence O(sqrt(n)) ~ O(e^(-n)) iff O(n^n) ~ O(n!).
But O(sqrt(n)) ~ O(e^(-n)) is false.
Therefore O(n^n) ~ O(n!) is false.
Since n! < n^n, we have n! = o(n^n). QED.


Here is another proof from djfm which does not rely on Stirling's approximation:

这篇关于安排他们的大哦，复杂性增加的顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！