大 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