算法的复杂度，也就是算法的时间或空间量度，记作：$T(n)= O(f(n))$。
用大写$O()$来体现算法复杂度的记法，我们称之为 大O记法。
一般情况下，随着输入规模n的增大，$T(n)$增长最慢的算法为最优算法。
函数增长曲线
A log-log-scaled plot of different functions (including polynomially and exponentially growing ones as well as the factorial) to illustrate the speed of growth of these functions. Exponential functions grow very fast, so that an algorithm which needs $ ~ 2^x $ steps to solve an optimization problem of size $x$ quickly becomes infeasible.
Big-O Complexity Chart
常见的算法时间复杂度有： $O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!)$
复杂度对应的名称分别是：常数阶，对数阶，线性阶，二维阶，平方阶，立方阶，指数阶，乘阶阶
Horrible |
Bad |
Fair |
Good |
Excellent |
一些常用数组排序算法的时间复杂度和空间复杂度
| Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best | Average | Worst | Worst | |
| Quicksort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(log(n)) |
| Mergesort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Timsort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Heapsort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(1) |
| Bubble Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Insertion Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Selection Sort | Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
| Tree Sort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(n) |
| Shell Sort | Ω(n log(n)) |
Θ(n(log(n))^2) |
O(n(log(n))^2) |
O(1) |
| Bucket Sort | Ω(n+k) |
Θ(n+k) |
O(n^2) |
O(n) |
| Radix Sort | Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| Counting Sort | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
| Cubesort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
一些常用数据结构的时间复杂度和空间复杂度
| Data Structure | Time Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| Array | Θ(1) |
Θ(n) |
Θ(n) |
Θ(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
| Stack | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Queue | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Singly-Linked List | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Doubly-Linked List | Θ(n) |
Θ(n) |
Θ(1) |
Θ(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Skip List | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log(n)) |
| Hash Table | N/A |
Θ(1) |
Θ(1) |
Θ(1) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| Binary Search Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
| Cartesian Tree | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(n) |
O(n) |
O(n) |
O(n) |
| B-Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Red-Black Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| Splay Tree | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
N/A |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| AVL Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
| KD Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
参考
- https://thomasweise.github.io/aitoa/aitoa.html
- https://www.bigocheatsheet.com/
PREVIOUSjava 位运算符!