Алгоритмы и структуры данных — как это работает

Последовательность чётких шагов для решения задачи. Должен завершаться за конечное время и давать одинаковый результат для одних и тех же входных данных.

Способ описать, как растёт время/память при увеличении размера входных данных. O(n) — «растёт пропорционально n». Не точное число операций, а порядок сложности.

Упорядочивание элементов по заданному критерию. Один из самых изученных классов алгоритмов. Нет универсально «лучшей» — каждый алгоритм оптимален в своих условиях.

Сохраняет относительный порядок элементов с одинаковыми ключами. Merge sort — стабильна, quick sort — нет. Важно при многоуровневой сортировке объектов.

Не использует дополнительную память пропорционально n. Quick sort и heap sort — in-place (O(log n) стека). Merge sort требует O(n) доп. памяти.

Способ организации и хранения данных в памяти. Определяет сложность операций доступа, поиска, вставки и удаления. Правильный выбор важнее оптимизации кода.

Последовательность элементов одного типа в непрерывном блоке памяти. O(1) доступ по индексу, кэш-дружелен. Вставка/удаление в середину — O(n).

Цепочка узлов, каждый из которых содержит данные и указатель на следующий. O(1) вставка при наличии указателя на позицию, O(n) доступ по индексу.

LIFO-структура: последний добавленный элемент извлекается первым. Push и Pop — O(1). Используется в стеке вызовов, undo/redo, DFS, проверке скобок.

FIFO-структура: первый добавленный элемент извлекается первым. Enqueue и Dequeue — O(1). Используется в BFS, очередях задач, буферах данных.

Структура ключ-значение с O(1) операциями в среднем. Использует хеш-функцию для вычисления позиции элемента. Основа словарей, кэшей и множеств.

Ситуация, когда два разных ключа дают одинаковый хеш. Обрабатывается цепочками (separate chaining) или открытой адресацией (open addressing).

Дерево, где для каждого узла: все в левом поддереве меньше, в правом — больше. O(log n) при сбалансированном. Деградирует до O(n) без балансировки (AVL/Red-Black).

Бинарное дерево, где родитель всегда ≥ (max-heap) или ≤ (min-heap) потомков. O(1) доступ к максимуму/минимуму. Основа Priority Queue и алгоритма Дейкстры.

Очередь, где каждый элемент имеет приоритет. Извлекается всегда элемент с наивысшим приоритетом. Реализуется через heap.

Набор вершин (V) и рёбер (E). Бывает ориентированный/неориентированный, взвешенный/невзвешенный. Моделирует дороги, соцсети, зависимости пакетов, интернет-маршруты.

Обход графа уровень за уровнем. Находит кратчайший путь в невзвешенном графе. Использует очередь. O(V+E).

Обход графа, идя как можно глубже перед возвратом. Использует стек (или рекурсию). Находит циклы, топологическую сортировку, связные компоненты. O(V+E).

Находит кратчайший путь от источника до всех вершин в взвешенном графе с неотрицательными весами. Использует min-heap. O((V+E) log V).

Функция, которая вызывает сама себя. Требует базового случая для остановки. Каждый вызов добавляет кадр в стек вызовов. Может переполнить стек при глубокой рекурсии.

Кэширование результатов функции для одинаковых аргументов. Основа динамического программирования. Превращает экспоненциальную рекурсию в линейную (напр., фибоначчи).

Стратегия: разбить задачу на подзадачи, решить каждую рекурсивно, объединить результаты. Основа merge sort, quick sort, бинарного поиска. Даёт O(n log n) для сортировки.

Средняя сложность операции с учётом всей последовательности вызовов. Push в динамический массив — O(1) амортизированно: иногда O(n) на удвоение, но суммарно дёшево.