Big-O 渐近增长率排序函数

Question

这是我按渐近增长率递增顺序排列的函数。另外，我通过应用对数规则简化了一些函数。

1. log( log n )
2. sqrt( log n )
3. log n^3（等于 log n）
4. n^2/3
5. 2^logn（等于 n）
6. n 日志 n
7. n^2

这个顺序正确吗？还是我遗漏了什么？

Answer 1

O( A(n) ) < O( B(n) ) 成立当且仅当 A(n) / B(n) 接近 0 当 n 趋于无穷大时。

您可以在此处查看您的 table：https://www.wolframalpha.com/input/?i=limit+log%28log%28n%29%29+%2F+sqrt%28log%28n%29%29%2C+n+to+infinity

例如

log(log(n)) / sqrt(log(n)) -> 0 for n -> inf

因此O(log(log(n)) < O(sqrt(log(n)).