sottoВыбор структуры данных определяет сложность операций. Поиск в массиве — O(n), в хеш-таблице — O(1), в сбалансированном дереве — O(log n).
| структура | доступ | поиск | вставка | где в языке |
|---|---|---|---|---|
| динамический массив | O(1) | O(n) | O(1) в конец | Array, list, ArrayList, срез Go |
| хеш-таблица | — | O(1) | O(1) | Map/Set, dict, HashMap, map |
| связный список | O(n) | O(n) | O(1) при известном узле | LinkedList |
| куча | минимум O(1) | — | O(log n) | heapq, PriorityQueue |
| дерево поиска | — | O(log n) | O(log n) | TreeMap, индексы БД |
Что важно знать
- Как устроена хеш-таблица: хеш-функция, коллизии, расширение — и почему ключ должен быть неизменяемым.
- Стек (последним пришёл — первым ушёл): вызовы функций, отмена действий, проверка скобок. Очередь: обработка задач, обход в ширину.
- Куча — быстрый доступ к минимуму: приоритетные очереди, топ-K.
- Деревья: DOM — дерево, индексы баз данных — B-деревья, JSON — дерево.
- Амортизированная сложность: почему добавление в конец динамического массива — O(1), хотя иногда он копируется целиком.