大 O 符号混淆

Question

从最小到最大排序并想知道我在哪里犯了错误？等价物在同一行。我真的很困惑 O(sqrt(n)) 会在列表中的哪个位置？1. O(log n)2. O(n)3. O(2^2 n)4. O(2n log n)5. O(n log n)6. O(n log n^2)7. O(sqrt(n))8. O(n^1.5) 9. O(n^2)   O(2n^2)  O(n^2 log n)10. O(n^3)11. O(k^2) O(2^n)

Answer 1

这可能会帮助您更好地理解复杂物的顺序。

Answer 2

O( ) 为方便省略：

k^2 (assuming k is constant??)  

log n 

sqrt n == n^0.5   

n == (2^2) n   

n log n == 2n log n == n log(n^2)   

n^1.5  

n^2 == 2n^2  

n^2 log n  

n^3  

2^n