algorithm - 按 Big O Complexity 的递增顺序排列

Question

如果给定

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 复杂度的递增顺序)将是

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 是一个大数时。是吗？

Answer 1

总而言之，就大 Oh 复杂度而言，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!

这Wikipedia page您可能会感兴趣。

编辑:关于 n!与 n^n

使用斯特林近似，我们有:

因此 O(n!) ~O(sqrt(n) * n^n * e^(-n))
因此 O(sqrt(n)) ~ O(e^(-n)) 当且仅当 O(n^n) ~ O(n!)。
但是 O(sqrt(n)) ~ O(e^(-n)) 是假的。
因此 O(n^n) ~ O(n!) 为假。
自从 n! < n^n，我们有 n! =o(n^n)。 QED.


这是来自 djfm 的另一个证明它不依赖于斯特林的近似: