Правильный выбор структуры данных часто важнее самого алгоритма. Метод простой: найдите главную операцию, посмотрите на ограничения, возьмите самый простой готовый тип и проверьте выбор подсчётом операций. В прошлом уроке был каталог ADT; этот урок превращает его в правило выбора.
Выбор по главной операции
Разложите задачу на операции: поиск, вставка, удаление, порядок, минимум/максимум, запрос по диапазону. Выбор определяет самая частая операция на самом большом n. Затем посмотрите на ограничения: память, дубликаты, хешируемость ключей, важность порядка. Цены основных структур:
| Структура | Поиск | Вставка | Min / порядок |
|---|---|---|---|
list | O(n) | в конец O(1), в середину O(n) | O(n) |
| отсортированный список | O(log n) | O(n) | O(1) |
deque | O(n) | O(1) с обоих концов | O(n) |
set / dict | O(1) в среднем | O(1) в среднем | O(n) |
heapq | O(n) | O(log n) | O(1) |
Более точные цены — в уроке про сложность встроенных операций.
