| Оператор сравнения асимптотических оценок | Оператор сравнения чисел |
|---|---|
| Алгоритм является o( что-то ) | Число < чего-то |
| Алгоритм является O( что-то ) | Число <= чего-то |
| Алгоритм является Θ( что-то ) | Число = чего-то |
| Алгоритм является Ω( что-то ) | Число >= чего-то |
| Алгоритм является ω( что-то ) | Число > чего-то |
| 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) |
| Data Structure | Time Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| Array | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| Hash table | N/A | O(1) | O(1) | O(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) |
| 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) |
| B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
- Введение в анализ сложности алгоритмов (часть 1). Available at: https://habrahabr.ru/post/196560
- Введение в анализ сложности алгоритмов (часть 2). Available at: https://habrahabr.ru/post/195482/
- Введение в анализ сложности алгоритмов (часть 3). Available at: https://habrahabr.ru/post/195996/
- Введение в анализ сложности алгоритмов (часть 4). Available at: https://habrahabr.ru/post/196226/
- Big-O Algorithm Complexity Cheat Sheet. Available at: http://bigocheatsheet.com
- Знай сложности алгоритмов. Available at: https://habrahabr.ru/post/188010
- Оценка сложности алгоритмов. Available at: https://habrahabr.ru/post/104219