Глоссарий — DSA 01

Асимптотическая верхняя граница роста функции. f(n) = O(g(n)) означает, что при больших n значение f(n) не превышает константу, умноженную на g(n). Используется для описания худшего случая времени или памяти алгоритма, отбрасывая константы и младшие члены.

Асимптотически точная граница. f(n) = Theta(g(n)) означает, что f(n) ограничена и сверху, и снизу константами, умноженными на g(n). Сильнее, чем Big-O: Theta(n) — это и O(n), и Omega(n) одновременно.

Асимптотическая нижняя граница. f(n) = Omega(g(n)) означает, что f(n) растёт не медленнее, чем константа, умноженная на g(n). Используется для нижних границ алгоритмов (например, сортировка сравнениями — Omega(n log n)).

Метод анализа, при котором стоимость операции усредняется по последовательности из N операций. Отдельная операция может быть дорогой (resize массива — O(n)), но в среднем по последовательности она дешёвая (append — O(1) amortized). Это не то же самое, что average case.

Простейший способ доказать амортизированную сложность: посчитать суммарную стоимость T(n) для последовательности из n операций и поделить на n. Для x2 dynamic array сумма работы copy при resize — геометрическая прогрессия, меньше 2n, что даёт amortized O(1) на append.

Банковский метод амортизации: каждой операции назначается амортизированная плата (больше реальной), излишек откладывается в «банк». Дорогие операции (resize) оплачиваются из банка. Если банк никогда не уходит в минус, амортизированная плата — корректная верхняя граница.

Формальный метод амортизации: вводится функция потенциала Phi от состояния структуры, amortized cost = actual cost + delta(Phi). Если Phi >= 0 и Phi_initial = 0, сумма amortized — верхняя граница реальной стоимости. Используется для сложных структур: splay tree, Fibonacci heap.

Зависимость количества элементарных операций алгоритма от размера входа n. Меряется в Big-O: O(1) — константа, O(log n) — логарифм, O(n) — линейно, O(n log n) — сортировка сравнениями, O(n^2) — квадрат, O(2^n) — экспонента.

Зависимость объёма памяти, нужного алгоритму, от размера входа n. Включает auxiliary space (рабочая память) и input space (сам вход). BFS — O(n) по памяти (нужна очередь), DFS — O(h) (глубина стека).

Класс задач, решаемых за полиномиальное время O(n^k) для константы k. Сюда входят сортировки, поиск, графовые обходы, кратчайшие пути. «Эффективно решаемые» в теоретическом смысле.

Класс задач, решение которых можно проверить за полиномиальное время. Сюда входят все задачи из P, плюс задачи, для которых решения мы пока умеем находить только перебором (SAT, коммивояжёр). Открытый вопрос: P = NP?

Самые «трудные» задачи в NP: если для любой NP-complete найдётся полиномиальный алгоритм, то P = NP. Классические примеры: SAT, 3-COLOR, TSP, subset sum. На практике решаются эвристиками и приближёнными алгоритмами.

Структура данных с фиксированным размером, элементы которой лежат в непрерывной памяти по равным offset-ам. Доступ по индексу — O(1). В Python чистого статического array нет; есть module array и numpy.ndarray для однотипных элементов.

Массив, который умеет расти при заполнении: при достижении ёмкости выделяется новый буфер большего размера (обычно x2 или x1.125), элементы копируются. Append амортизированно O(1), вставка в середину O(n). В Python это PyListObject.

Структура данных, в которой каждый элемент (узел) хранит данные и указатель на следующий узел. Узлы лежат в произвольных местах памяти. Insert/delete в начало — O(1), доступ по индексу — O(n). На современном железе медленнее массива из-за pointer chasing.

Связный список, в котором каждый узел хранит указатель только на следующий. Удаление текущего узла за O(1) невозможно без предыдущего узла. Меньше памяти на узел, чем у doubly linked.

Связный список, в котором каждый узел хранит указатели и на следующий, и на предыдущий. Позволяет O(1) удаление узла, если есть ссылка на него. Используется внутри collections.deque и LRU cache.

LIFO-структура: push и pop работают с одного конца. O(1) на обе операции. Реализуется поверх dynamic array (Python list) или связного списка. Применяется в DFS, парсерах, undo-историях, call stack.

FIFO-структура: enqueue в конец, dequeue из начала. O(1) на обе операции в правильной реализации. В Python — collections.deque, не list (list.pop(0) — O(n)).

Double-ended queue — структура, которая поддерживает O(1) добавление и удаление с обоих концов. В CPython collections.deque реализован как doubly linked list блоков (по 64 элемента в блоке), а не как массив.

Циклический массив фиксированного размера с двумя указателями (head и tail). Push/pop с обоих концов — O(1). Используется в low-latency-системах, аудио-буферах, network drivers. Хорошая spatial locality в отличие от связных списков.

Структура key -> value, использующая хеш-функцию для размещения ключа в bucket. Средняя сложность операций — O(1), худший случай — O(n) при плохом хеше. В Python это dict, реализованный через open addressing с perturbation.

Множество уникальных элементов на основе хеш-таблицы. В Python — set/frozenset. Внутренне почти идентичен dict, но без значений. O(1) на add/remove/in в среднем.

Binary search tree — бинарное дерево, в котором для каждого узла левое поддерево содержит ключи меньше узла, правое — больше. Поиск, вставка, удаление — O(h), где h — высота. Без балансировки h может выродиться в n. Балансированные варианты: AVL, red-black.

Полное бинарное дерево, хранящееся в массиве, со свойством heap (родитель меньше или равен детям для min-heap). Insert и extract-min — O(log n), peek — O(1). Используется для priority queue и heap sort. Дети узла i лежат на 2i+1 и 2i+2.

Куча, в которой корень — минимальный элемент. Используется в priority queue (sched), top-K largest (хранить top-K через min-heap размера K), Dijkstra. Python heapq реализует именно min-heap.

Куча, в которой корень — максимальный элемент. Применяется в heap sort, top-K smallest (через max-heap размера K), task schedulers. В Python максимум через heapq делается через инверсию знаков или кортежи (-key, value).

Структура из вершин (V) и рёбер (E), описывающая отношения. Бывает направленный или ненаправленный, взвешенный или нет. Используется в DE для lineage, DAG-ов оркестрации (Airflow), графов транзакций. Представления: adjacency matrix, adjacency list, CSR.

Представление графа квадратной матрицей V x V, где matrix[i][j] = 1 если есть ребро. Память O(V^2), проверка ребра — O(1), обход соседей — O(V). Выгодна для плотных графов и алгоритмов вроде Floyd-Warshall.

Представление графа как dict (или массив) списков: для каждой вершины — список соседей. Память O(V + E), обход соседей — O(degree). Выгодно для разреженных графов. В Python обычно dict[int, list[int]] или defaultdict(list).

Compressed Sparse Row — компактное представление графа двумя массивами: offsets (где начинаются соседи каждой вершины) и indices (сами соседи). Отличная spatial locality, в 2-4 раза быстрее adjacency list в обходах. Используется в scipy.sparse, NetworkX-аналогах для больших графов.

Минимальная единица, которой CPU читает из RAM в кэш — 64 байта на современных x86 и ARM. Чтение одного байта физически невозможно — всегда подгружаются 64 байта, выровненных по границе. Это основа spatial locality.

Первый уровень кэша CPU — обычно 32-64 KB на ядро, latency ~1 ns (3-4 такта). Разделён на L1d (данные) и L1i (инструкции). Самый быстрый, но самый маленький. Промах в L1 ведёт к чтению из L2.

Второй уровень кэша — обычно 256 KB - 1 MB на ядро, latency ~3-5 ns (10-15 тактов). Больше L1, медленнее. Промах ведёт к L3 или RAM.

Третий уровень кэша — обычно 4-64 MB, общий для всех ядер сокета. Latency ~10-20 ns. Последний уровень перед RAM. Промах — это уже ~60-100 ns на чтение из RAM.

Random Access Memory — основная память. Latency ~60-100 ns на чтение, в 60-100 раз медленнее L1. Чтение всегда выровнено по cache line. Имя «random access» обманчиво: последовательный доступ быстрее случайного из-за prefetcher и cache lines.

Свойство паттерна доступа: если код обращается к адресу X, скоро понадобятся X+1, X+2 и так далее. Превращает дорогие RAM-чтения в почти бесплатные cache hits. Хорошо: проход по массиву. Плохо: random access, linked list.

Свойство: если код обратился к X, скоро обратится к X снова. Cache держит недавние данные именно ради этого. Хорошо: переменная цикла в регистре, hot-data в hash-таблице. Плохо: однократный проход через гигантский dataset.

Аппаратный механизм CPU, который предсказывает следующие читаемые адреса и заранее подгружает их в кэш. Хорошо работает на sequential access. Не работает на linked list — указатели непредсказуемы.

Аппаратный механизм CPU: пытается предсказать, по какой ветке пойдёт if, чтобы не останавливать конвейер. Промах предсказания (branch misprediction) — 10-20 тактов простоя. Хорошо предсказываются монотонные паттерны (отсортированный массив), плохо — случайные.

Конвейерное исполнение инструкций в CPU: пока одна инструкция декодируется, следующая уже читает операнды, следующая исполняется. На современных CPU — 14-20 стадий. Промах branch prediction или cache miss обнуляет полезную работу нескольких стадий.

Паттерн доступа, при котором каждый следующий адрес становится известен только после чтения предыдущего (next = node.next). Prefetcher беспомощен, каждая итерация — потенциальный cache miss. Отсюда — медленность linked list, BST, graph через объекты.

Последовательный проход по памяти с постоянным offset (arr[0], arr[1], arr[2]). Оптимальный паттерн: prefetcher успевает подгружать следующие cache lines, каждый доступ — cache hit. Основа быстрых обходов массивов и numpy.

Иерархия памяти: регистры (sub-ns) -> L1 (1 ns) -> L2 (3-5 ns) -> L3 (10-20 ns) -> RAM (60-100 ns) -> SSD (10000 ns) -> HDD (10 ms). Каждый уровень в 3-100 раз медленнее предыдущего. DSA-выбор должен учитывать, в какой уровень попадут данные.

Breadth-first search — обход графа по уровням: сначала все соседи стартовой вершины, потом их соседи, и так далее. Использует очередь (collections.deque). Сложность O(V + E). Находит кратчайший путь в невзвешенном графе. Память — O(V).

Depth-first search — обход графа в глубину: спускаемся по одной ветке как можно глубже, затем откат. Использует стек (рекурсия или явный stack). O(V + E) по времени, O(h) по памяти, где h — глубина. Основа топологической сортировки.

Поиск элемента в отсортированном массиве делением пополам: O(log n). Реализован в bisect (Python). Тонкие места: off-by-one на границах, выбор upper vs lower bound, обработка дубликатов. Не работает на linked list — нужен random access.

Поиск элемента простым проходом: O(n) в худшем случае. На малых n (десятки элементов) обгоняет binary search и hash из-за лучшей cache locality и отсутствия overhead. Лучший выбор для коротких списков.

Простая сортировка: проходим массив, меняем соседей местами если нарушен порядок, повторяем. O(n^2) в худшем и среднем случае. Стабильная. Практически нигде не используется, кроме учебных целей.

Сортировка вставками: берём элемент, сдвигаем влево, пока не найдёт своё место. O(n^2) в худшем, O(n) на почти отсортированном. Используется как «нижний этаж» Timsort и introsort для малых подмассивов (обычно n < 32-64).

Сортировка выбором: находим минимум в неотсортированной части и ставим в начало. O(n^2) всегда, не зависит от входных данных. Делает минимум swap-ов — O(n). Используется редко, в основном на embedded.

Сортировка слиянием: рекурсивно делим массив пополам, сортируем половины, сливаем. O(n log n) по времени всегда. O(n) дополнительной памяти. Стабильная. Базис Timsort и внешней сортировки (k-way merge на дисках).

Сортировка через partitioning вокруг pivot. Среднее — O(n log n), худший случай — O(n^2) (плохой pivot). Не стабильная, in-place. С randomized pivot или median-of-three используется в introsort (libc++, .NET).

Гибридная стабильная сортировка, использующая insertion sort на малых блоках (runs) и merge sort для их слияния. Использует естественно отсортированные участки. O(n log n) в худшем, O(n) на отсортированном. Стандартная сортировка в Python и Java.

Сортировка через построение max-heap и последовательный extract-max. O(n log n) в худшем случае, in-place. Не стабильная. Хуже Timsort на cache locality (произвольные обмены в массиве), используется реже.

Не-сравнительная сортировка: распределяем элементы по «корзинам» по цифрам/битам, повторяя по разрядам. O(n * k), где k — длина ключа. Работает только на целых или строках фиксированной длины. Быстрее O(n log n) при больших n и коротких ключах.

Не-сравнительная сортировка для целых из малого диапазона [0, k]: считаем сколько раз встретился каждый ключ, потом раскладываем. O(n + k) по времени и памяти. Стабильная. Используется как «низший уровень» radix sort.

Операция разделения массива относительно pivot: слева — меньше или равно, справа — больше. Базовая операция quicksort. Lomuto и Hoare — два классических варианта. Один проход — O(n).

Построение кучи из массива за O(n) (а не O(n log n), как могло бы показаться). Идея: пройти от середины массива к началу, для каждого узла «просеять» вниз. Используется при инициализации heap (heapq.heapify).

Слияние k отсортированных последовательностей в одну. Через min-heap размера k: O(N log k), где N — суммарное число элементов. Основа external sort и merge-операции в Spark/Flink shuffle.

Парадигма: задачу делим на меньшие подзадачи того же типа, решаем рекурсивно, объединяем. Merge sort, quicksort, binary search, FFT, Strassen. Анализ через рекуррентные соотношения и Master Theorem.

C-структура CPython, реализующая list. Содержит указатель на массив PyObject*, длину и ёмкость. При переполнении ёмкости growth-формула CPython: new = (old + (old >> 3) + 6) & ~3 — рост примерно x1.125, не x2.

Указатель на структуру PyObject — представление любого Python-объекта на уровне C. В list хранятся именно указатели (8 байт на 64-битке), а не сами объекты. Поэтому list[int] на 1M элементов весит около 36 MB (8 байт на указатель плюс 28 байт на сам PyLongObject), а не 4 MB.

Стратегия поиска свободного слота в Python dict при коллизии: j = (5*j + 1 + perturb) & mask, perturb >>= 5. Использует все биты хеша через perturbation, гарантирует обход всех слотов до повторения.

Техника в Python dict probing: переменная perturb, изначально равная полному хешу, сдвигается на 5 битов каждую итерацию. Подключает старшие биты хеша к probing — ключи с одинаковыми младшими битами расходятся по разным слотам.

Криптографически безопасная хеш-функция, которую CPython использует для hash(str), hash(bytes). Защищает от hash-flooding атак: при старте процесса генерируется случайный seed (PYTHONHASHSEED), поэтому hash(s) одной строки разный между запусками.

Функция CPython: возвращает размер объекта в байтах без учёта объектов, на которые он ссылается. Поэтому sys.getsizeof([1,2,3]) даёт размер самого list-объекта (~88 байт), но не учитывает int-ов внутри. Для глубокого размера — pympler.asizeof.

Утилита для рекурсивного измерения памяти Python-объектов: считает размер вместе со всеми ссылками, обрабатывая циклы. Медленнее sys.getsizeof, но даёт реальное потребление памяти структурой.

Модуль stdlib для микро-бенчмаркинга Python-кода: запускает фрагмент N раз, выключая GC, и возвращает время. timeit.timeit(stmt, number=10000) — основа всех измерений в курсе. Чувствителен к шуму CPU, fan-curve, фоновым процессам.

Модуль stdlib для трекинга аллокаций памяти Python-программы. Показывает, где (по строкам кода) и сколько байт было выделено. Лучше sys.getsizeof для поиска утечек и узких мест в реальных пайплайнах.

Двусторонняя очередь CPython, реализованная как doubly linked list блоков по 64 указателя. appendleft, append, popleft, pop — O(1). Используется для BFS, sliding window, history buffer. Быстрее list для head-операций.

Модуль stdlib для работы с min-heap поверх обычного list. heappush, heappop — O(log n). heapify — O(n). nlargest, nsmallest — частые операции для top-K. Не имеет max-heap — нужна инверсия знаков.

Чистый Python-пакет, дающий SortedList/SortedDict/SortedSet с O(log n) на insert/delete/lookup. Внутри — список списков (B-tree-подобная структура), а не RB-tree. На практике быстрее BST из-за cache locality.

Global Interpreter Lock — глобальная блокировка CPython, разрешающая исполнять Python-байткод только одному потоку за раз. Из-за GIL multi-threading в Python не даёт CPU-параллелизма на чистом Python-коде. В 3.13 появился экспериментальный no-GIL build.

Reference counting — основной механизм управления памятью в CPython. Каждый объект хранит счётчик ссылок, при достижении нуля объект освобождается. Видно через sys.getrefcount(obj). Не справляется с циклическими ссылками — для них есть GC.

Задача: найти K самых больших (или маленьких) элементов в потоке из N. Наивно через sort — O(N log N). Через min-heap размера K — O(N log K), сильно лучше при K << N. Базовый паттерн в DE: top-N клиентов по выручке.

Дедупликация — удаление повторяющихся записей. Через set — O(N) по времени, O(N) по памяти. На миллиардах записей set не помещается в RAM — нужны Bloom filter (вероятностный) или внешняя сортировка с merge.

Вероятностная структура для проверки принадлежности множеству. Битовый массив + k хеш-функций. Не даёт false negatives (если говорит «нет», то точно нет), но допускает false positives. В 8-10 раз меньше памяти, чем set. Используется в Cassandra, HBase, RocksDB.

Окно фиксированного размера W, которое скользит по потоку: на каждом шаге добавляется новый элемент справа, выкидывается крайний слева. O(1) на шаг через deque или ring buffer. Базовый паттерн стриминговых агрегаций.

Не-перекрывающееся окно фиксированного размера: события группируются в блоки по времени или количеству. Используется в Flink/Spark Structured Streaming для агрегаций по периодам (минуты, часы).

Окно переменного размера, определяемое gap-ом неактивности: события одной сессии группируются, пока разрыв между ними меньше threshold. Используется для аналитики поведения пользователей: визит на сайт, активность в приложении.

Сортировка данных, не помещающихся в RAM. Классический алгоритм: разделить на чанки по размеру памяти, отсортировать каждый, записать на диск, сделать k-way merge на дисках. O(N log N) по сравнениям, но с минимизацией I/O.

DAG зависимостей между датасетами и трансформациями в пайплайне: какая таблица из какой получена и какой операцией. Хранится в Marquez, DataHub, OpenLineage. Используется для impact analysis и debug «откуда взялась эта строчка».

Directed acyclic graph — направленный граф без циклов. Базовая абстракция оркестраторов (Airflow, Dagster, Prefect): вершины — задачи, рёбра — зависимости. Допускает топологическую сортировку — порядок исполнения задач.

Линейный порядок вершин DAG, в котором каждое ребро направлено вперёд. Алгоритм Кана: O(V + E) через очередь вершин с in-degree=0. Используется в оркестраторах для определения порядка задач, в build-системах, при проверке зависимостей пакетов.

Least-Recently-Used cache — хранит K последних использованных элементов, при переполнении выкидывает least-recently-used. Реализуется через doubly linked list + hash map: O(1) на get и put. В Python — functools.lru_cache.