Конспект: структуры данных и алгоритмы¶
Самодостаточный конспект по всем сущностям из лабораторных работ. Каждый раздел содержит: что это, зачем нужно, как устроено, сложность операций и работающий пример кода. Читается без обращения к исходникам репозитория.
Разделы по лабораторным¶
- common — общие утилиты
Переиспользуемые helper'ы
array_length,generate_array,print_arrayи самописныйcustom_rangeиз пакетаlabs/common. - lab01 — массив и стек
Массив без встроенных
len/range/max/sumи стек (LIFO) на его основе. - lab02 — связный список, очередь, дерево Односвязный список, очередь (FIFO) на двух указателях, бинарное дерево поиска и его визуализация.
- lab02_random — случайные данные и баланс
Тот же набор структур, но со случайным заполнением и сбалансированным деревом через
build_balanced. - lab03 — сортировки и подсчёт перестановок Сортировки выбором, вставками, пузырьковая и быстрая со счётчиком перестановок, их сравнение и меню.
- lab04 — поиск: линейный и бинарный Поиск перебором (true/false, индекс, все индексы, количество) и бинарный поиск по отсортированному массиву.
- lab05 — hash map и разрешение коллизий Хеш-таблица «с нуля»: метод цепочек и открытая адресация (линейное пробирование, двойное хеширование), надгробия при удалении, load factor и rehash.
Прикладные расширения (под SRE/DevOps)¶
- lab00 — Python для эксплуатации
Файлы и контекстные менеджеры, аргументы командной строки (
argparse) и коды возврата, исключения как контракт, генераторы и итераторы. Ступенька до структур данных. - lab06 — графы и топологическая сортировка Граф на списке смежности, обходы BFS/DFS, обнаружение цикла, топосортировка (порядок с учётом зависимостей).
- lab07 — куча и top-K Бинарная min/max-куча на массиве, приоритетная очередь, выбор K крупнейших без полной сортировки.
- lab08 — LRU-кэш
Хеш-таблица + двусвязный список:
get/putза O(1) и вытеснение Least Recently Used. - lab09 — rate limiting Кольцевой буфер, token bucket, leaky bucket, sliding window (с инъекцией времени для детерминизма).
- lab10 — разбор логов Потоковая обработка через генераторы, агрегация по полям, перцентили латентности p50/p95/p99.
- lab11 — consistent hashing и bloom filter
Хеш-кольцо с виртуальными нодами (почему
hash % Nломается при добавлении ноды) и вероятностный bloom filter.
Сводная таблица сложности¶
| Структура / операция | Время | Комментарий |
|---|---|---|
| Массив: доступ по индексу | O(1) | arr[i] |
| Массив: поиск max / суммы | O(n) | один проход |
| Стек: push / pop / peek | O(1) | работа с концом списка |
| Связный список: add (в конец) | O(n) | нет хранения хвоста |
| Связный список: remove / поиск | O(n) | перебор от головы |
| Очередь: enqueue / dequeue | O(1) | хранятся оба указателя head и tail |
| BST: add / поиск (сбаланс.) | O(log n) | высота ≈ log₂(n) |
| BST: add / поиск (вырожден.) | O(n) | отсортированный ввод → «список» |
| build_balanced | O(n log n) | из-за сортировки |
| Обход / печать любой структуры | O(n) | посещаем все элементы |
| Сортировка выбором | O(n²) | ≤ n−1 перестановок, сравнений всегда максимум |
| Сортировка вставками | O(n²) | O(n) на почти отсортированных данных |
| Пузырьковая сортировка | O(n²) | O(n) на отсортированных (ранний выход) |
| Быстрая сортировка | O(n·log n) | в среднем; в худшем случае O(n²) |
| Линейный поиск (перебором) | O(n) | работает на любом массиве |
| Бинарный поиск | O(log n) | только на отсортированном массиве |
| Hash map: put / get / delete | O(1) | в среднем при хорошем хеше и контроле load factor |
| Hash map: put / get / delete (худшее) | O(n) | все ключи в одну ячейку (плохой хеш) |
| Hash map: rehash (resize) | O(n) | перехеширование всех пар при расширении |
| Граф: BFS / DFS обход | O(V+E) | посещаем все вершины и рёбра |
| Граф: топологическая сортировка | O(V+E) | алгоритм Кана по степеням входа |
| Куча: push / pop | O(log n) | просеивание по высоте дерева |
| Куча: peek / build (heapify) | O(1) / O(n) | вершина — корень; построение линейно |
| top-K через кучу | O(n·log k) | куча размера K вместо полной сортировки |
| LRU-кэш: get / put | O(1) | hash map + двусвязный список |
| Rate limiter: allow | O(1) | token/leaky bucket; sliding window — амортизированно |
| Consistent hashing: get_node | O(log V) | бинарный поиск по кольцу |
| Bloom filter: add / contains | O(k) | k хеш-функций; ложноотрицательных нет |
Ключевые выводы¶
- Массив — быстрый доступ по индексу O(1), но фиксирован по природе хранения.
- Связный список — гибкое добавление/удаление через перестановку ссылок, но нет доступа по индексу; всё через обход от головы.
- Стек (LIFO) и очередь (FIFO) — это дисциплины доступа, а не новые способы хранения; их можно строить и на массиве, и на связном списке.
- BST даёт быстрый поиск O(log n) — но только если дерево сбалансировано. Порядок вставки критичен;
build_balancedустраняет зависимость от него. - Рекурсия с «счётчиком в списке» (
[0]) — приём для сквозного изменяемого состояния через рекурсивные вызовы. - Сортировки сравнением (выбором, вставками, пузырёк) — все O(n²), но различаются по числу перестановок: выбором делает минимум обменов (≤ n−1), но максимум сравнений; вставки и пузырёк чувствительны к исходному порядку данных. Быстрая сортировка («разделяй и властвуй») в среднем O(n·log n) и на больших массивах обгоняет квадратичные, но в худшем случае (неудачный выбор опорного) деградирует до O(n²).
- Поиск: линейный (перебором) — O(n), работает на любых данных; бинарный — O(log n), но требует отсортированного массива. Бинарный поиск — классический пример размена: тратим O(n log n) на сортировку один раз, чтобы потом искать многократно за O(log n).
- Hash map даёт доступ по ключу за O(1) в среднем, вычисляя индекс как
hash(key) % capacityвместо перебора. Цена — коллизии (разные ключи → один индекс), которые неизбежны и требуют разрешения: метод цепочек складывает их в список бакета, открытая адресация ищет другой слот (линейное пробирование или двойное хеширование). Корректное удаление в открытой адресации требует надгробий (tombstone), иначе рвётся цепочка проб. Среднее O(1) держится только при хорошей хеш-функции и контроле load factor через авторасширение с перехешированием; иначе деградирует до O(n).