Структура | Временная сложность | Пространственная сложность | |||||||
---|---|---|---|---|---|---|---|---|---|
Средняя | Высокая | Высокая | |||||||
Доступ | Поиск | Вставка | Удаление | Доступ | Поиск | Вставка | Удаление | ||
Массив | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
Стек | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Очередь | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Односвязный список | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Двусвязный список | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Список с пропусками | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(nlog(n)) |
Хеш таблица | N/A | O(1) | O(1) | O(1) | N/A | O(n) | O(n) | O(n) | O(n) |
Двоичное дерево поиска | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
Декартово дерево | N/A | O(log(n)) | O(log(n)) | O(log(n)) | N/A | O(n) | O(n) | O(n) | O(n) |
B-дерево | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
Красно-черное дерево | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
Косое дерево | N/A | O(log(n)) | O(log(n)) | O(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
АВЛ-дерево | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
k-мерное дерево | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |