Справочник терминов

Абсолютная погрешность

Absolute error

Модуль разницы между приближением и истинным ответом.

Алгоритм

Algorithm

Конечная, определённая последовательность допустимых операций для решения формально поставленной задачи.

Алгоритм Штрассена

Strassen algorithm

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

Амортизированная оценка

Amortized bound

Оценка затрат последовательности операций.

Амортизированная стоимость

Amortized cost

Средняя стоимость операции в последовательности в смысле суммарной верхней оценки.

Амортизированный анализ

Amortized analysis

Метод оценки суммарной стоимости последовательности операций с учётом редких дорогих действий.

Базовый случай

Base case

Условие, при котором рекурсивный алгоритм завершается без дальнейших вызовов.

Биномиальная куча

Binomial heap

Лес min-деревьев разных рангов: на каждый ранг допускается не более одного дерева.

Биномиальное дерево

Binomial tree

Также: Биномиальное дерево Bₖ

Дерево, построенное связыванием двух деревьев Bₖ₋₁, одно становится ребёнком другого.

Битоническая последовательность

Bitonic sequence

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

Верхняя оценка O

Big O

Асимптотическая оценка сверху: f(n) ≤ Cg(n) для всех достаточно больших n.

Вещественный двоичный поиск

Real binary search

Бинарное сужение непрерывного интервала до нужной точности.

Время работы

Running time

Число элементарных действий в выбранной модели вычислений.

Входные данные

Input

Данные, которые алгоритм получает до или в процессе выполнения.

Выходные данные

Output

Результат выполнения алгоритма.

Глубина сети

Network depth

Число последовательных параллельных уровней.

Два стека

Two-stack queue

Также: Очередь на двух стеках

Реализация FIFO через два LIFO-контейнера.

FIFO через входной и выходной стеки.

Двоичная куча

Binary heap

Полное двоичное дерево со свойством кучи.

Двоичный поиск

Binary search

Логарифмическое сужение области ответа по монотонному условию.

Двоичный поиск по ответу

Binary search on answer

Поиск граничного параметра по проверке допустимости.

Двусвязный список

Doubly linked list

Список, где у каждого узла есть ссылки prev и next.

Деамортизация

Deamortization

Преобразование алгоритма с редкими дорогими операциями в алгоритм с распределённой работой и контролируемой стоимостью каждого шага.

Дерево рекурсии

Recursion tree

Схема вызовов, в которой вершины соответствуют задачам, а уровни показывают вложенность.

Дерево решений

Decision tree

Двоичная модель результатов сравнений.

Динамический массив

Dynamic array

Массив, который перевыделяется по мере заполнения.

Динамическое программирование

Dynamic programming

Метод решения задачи через сохранение ответов на повторяющиеся подзадачи и переходы между ними.

Инвариант

Invariant

Условие, сохраняющееся на этапах алгоритма.

Свойство, сохраняющееся после каждого шага.

Инвариант цикла

Loop invariant

Утверждение, сохраняющееся перед каждой итерацией цикла.

Инвариант min-кучи

Heap property

Для каждого узла значение его родителя не превосходит значения любого из его детей.

Инверсия

Inversion

Пара индексов i < j, для которой a[i] > a[j].

Каскадное разрезание

Cascading cut

Серия отделений помеченных вершин при decreaseKey.

Ключ

Key

Значение, по которому упорядочивают объект; сам объект может содержать и другие данные.

Кольцевой буфер

Circular buffer

Массив с циклическим переходом индексов.

Компаратор

Compare-exchange

Операция минимума/максимума пары.

Компаратор

Comparator / compare-exchange

Двухвходовая операция, направляющая минимум в один выход, максимум — в другой.

Компонента связности

Connected component

Класс вершин, соединённых путями в графе.

Консолидация

Consolidation

Слияние корней одинакового ранга после extractMin.

Константа

Constant factor

Множитель, не зависящий от размера входа n.

Копирование пути

Path copying

Создание новых узлов на пути к месту изменения.

Корзина

Bucket

Диапазон выходных позиций для конкретного ключа.

Коэффициент

Coefficient

Числовой множитель при данной степени переменной.

Левосторонняя куча

Leftist heap

Двоичная min-куча с ограничением на длины кратчайших путей к пустым детям: npl(left) ≥ npl(right).

Лес

Forest

Набор непересекающихся деревьев указателей.

Лучший случай

Best case

Минимальное время среди входов заданного размера.

Мастер-теорема

Master theorem

Правило оценки типовых рекуррентностей вида T(n)=aT(n/b)+Θ(n^c).

Математическое ожидание

Expectation

Среднее по возможным случайным исходам.

Матричное возведение

Matrix exponentiation

Ускорение повторного линейного преобразования.

Машинное слово

Machine word

Единица данных фиксированной для выбранной модели разрядности. Если значение не помещается в одно слово, его обработка может требовать нескольких операций.

Медиана

Median

Центральная порядковая статистика.

Медиана медиан

Median of medians

Детерминированный выбор хорошего опорного элемента по группам.

Мемоизация

Memoization

Кэширование результатов рекурсивных подзадач при первом обращении.

Метод бухгалтерии

Accounting method

Оплата будущих дорогостоящих действий накопленными кредитами.

Метод Карацубы

Karatsuba algorithm

Способ ускорить рекурсивное умножение, заменив четыре умножения половин тремя.

Минимакс

Minimax

Минимизация максимума некоторого семейства функций.

Многочлен

Polynomial

Сумма коэффициентов при неотрицательных целых степенях переменной.

Модель вычислений

Computational model

Условный набор разрешённых операций и их стоимостей, на котором оценивают алгоритм.

Монотонный предикат

Monotone predicate

Булева функция, у которой на упорядоченной области сначала все false, затем все true (или наоборот).

Нижняя граница

Lower bound

Также: Lower bound

Невозможность в данной модели работать асимптотически быстрее указанного порядка.

Индекс первого элемента массива, который не меньше x; если такого нет, возвращается n.

Нижняя оценка Ω

Big Omega

Асимптотическая оценка снизу: f(n) ≥ Cg(n) для всех достаточно больших n.

Нулевая длина пути

Null path length

Кратчайшее расстояние до отсутствующего ребёнка с выбранной нормировкой.

Обратная функция Аккермана

Inverse Ackermann

Очень медленно растущая функция α.

Обратная функция Аккермана

Inverse Ackermann function

Крайне медленно растущая функция, возникающая в точном амортизированном анализе DSU.

Объединение по рангу

Union by rank

Подвешивание дерева меньшего ранга под дерево большего.

Односвязный список

Singly linked list

Последовательность узлов, где каждый хранит значение и ссылку next на следующий узел.

Оптимальный предок

Predecessor

Состояние, откуда получен оптимальный переход.

Очередь

Queue

Контейнер с enqueue(x) и dequeue(): удаляется самый давно добавленный элемент (FIFO).

Очередь с приоритетами

Priority queue

Абстрактная структура, которая хранит элементы с приоритетами и позволяет добавлять элемент и извлекать наименьший (или наибольший).

Переход

Transition

Также: Переход состояния

Правило, вычисляющее вклад других состояний в текущее или будущие состояния.

Персистентная структура

Persistent data structure

Структура, у которой после обновления сохраняется доступ к предыдущим версиям состояния.

Полная персистентность

Full persistence

Обновление допустимо из любой предыдущей версии.

Полное бинарное дерево

Complete binary tree

Все уровни, кроме последнего, заполнены; последний заполняется слева направо.

Пометка

Mark

Флаг потери ребёнка в Fibonacci heap.

Порядковая статистика

Order statistic

Также: k-я порядковая статистика

Элемент с индексом k в мысленно отсортированном массиве; индексация с нуля.

Потенциал

Potential

Функция состояния, учитывающая запас накопленной работы.

Φ = число корней + 2 × число помеченных вершин.

Потенциал

Potential function

Неотрицательная величина, отражающая запас «отложенной» работы в текущем лесу.

Представитель

Representative

Выбранный корневой элемент класса.

Префиксная сумма

Prefix sum

Сумма элементов последовательности до заданной позиции.

Принцип 0–1

Zero-one principle

Сеть сравнений сортирует произвольные ключи тогда и только тогда, когда сортирует все последовательности из 0 и 1.

Просеивание вверх

Sift up

Восстановление свойства кучи после вставки.

Просеивание вниз

Sift down

Восстановление свойства кучи после замены корня.

Просмотр вперёд

Forward DP

Перенос вклада в будущие состояния.

Просмотр назад

Backward DP

Сбор ответа из предыдущих состояний.

Псевдокод

Pseudocode

Читаемая человеком запись алгоритма без строгого следования синтаксису языка программирования.

Разделение хвостов

Structural sharing

Несколько версий используют одни неизменяемые узлы.

Разделяй и властвуй

Divide and conquer

Подход: разделение задачи, рекурсивное решение подзадач и объединение результатов.

Размер входа n

Input size

Параметр, характеризующий масштаб экземпляра задачи.

Ранг

Rank

Вспомогательное значение корня, ограничивающее высоту дерева при union по рангу.

Ранг дерева

Degree / rank

Количество непосредственных детей вершины в рассматриваемой куче.

Рандомизированный алгоритм

Randomized algorithm

Алгоритм, который помимо входных данных использует случайные биты или случайный выбор.

Рекуррентность

Recurrence relation

Уравнение, выражающее время работы через значения для меньших размеров.

Рекуррентность

Recurrence

Равенство, связывающее значения задачи на разных состояниях.

Рекурсия

Recursion

Решение задачи через вызов того же алгоритма на меньшей подзадаче.

Свертка

Convolution

Операция r_k = Σ p_i q_(k−i), задающая коэффициенты произведения многочленов.

Сжатие путей

Path compression

После find(x) все вершины пройденного пути начинают непосредственно указывать на найденный корень.

Скобочная последовательность

Bracket sequence

Последовательность, корректность вложения которой проверяется стеком.

Слияние

Merge

Объединение двух отсортированных массивов в один отсортированный.

СНМ

DSU

Система непересекающихся множеств.

Сортировка

Sorting

Перестановка элементов в неубывающем порядке относительно выбранного сравнения.

Сортировка вставками

Insertion sort

Алгоритм, расширяющий отсортированный префикс вставкой очередного элемента на нужное место.

Сортировка слиянием

Merge sort

Рекурсивный алгоритм, разделяющий массив пополам и объединяющий отсортированные части.

Сортировочная сеть

Sorting network

Фиксированная схема компараторов: пары сравнений определены заранее и не зависят от входных значений.

Состояние

State

Компактное описание подзадачи.

Стек

Stack

Контейнер с операциями push(x) и pop(): удаляется последний добавленный элемент (LIFO).

Структура данных

Data structure

Представление данных вместе с набором поддерживаемых операций и оценками их стоимости.

Табуляция

Tabulation

Заполнение таблицы состояний в правильном порядке.

Табуляция

Bottom-up DP

Вычисление состояний в таком порядке, чтобы все зависимости уже были известны.

Тернарный поиск

Ternary search

Поиск экстремума унимодальной функции сравнением двух внутренних точек.

Топологический порядок

Topological order

Порядок, в котором зависимости обработаны раньше потомков.

Точная оценка Θ

Big Theta

Совместная асимптотическая оценка сверху и снизу с точностью до постоянных множителей.

Трёхчастное разбиение

Three-way partition

Группировка элементов меньше, равных и больше опорного.

Указатель

Pointer

Ссылка на другой узел модели.

Унимодальная функция

Unimodal function

Для поиска минимума — функция, которая сначала не возрастает, затем не убывает. В стандартном тернарном шаблоне ниже дополнительно требуем строгое убывание и возрастание вне области глобального минимума.

Устойчивая сортировка

Stable sort

Не меняет относительный порядок объектов с равными ключами.

Устойчивость

Stability

Сохранение относительного порядка равных ключей.

Фибоначчиева куча

Fibonacci heap

Лес деревьев min-кучи с ленивым объединением и амортизированными гарантиями для ключевых операций.

Фиктивная граница

Sentinel boundary

Логическая точка за массивом, не требующая обращения к памяти.

Фиктивный узел

Sentinel node

Служебный узел, упрощающий граничные случаи.

Худший случай

Worst case

Максимальное время среди входов заданного размера.

Циклический список

Circular linked list

Последний узел связан с первым или с фиктивным узлом.

BFPRT

Blum–Floyd–Pratt–Rivest–Tarjan

Детерминированный алгоритм линейной селекции.

Bottom-up

Снизу вверх

Вычисление состояния после зависимостей.

Counting sort

Counting sort

Сортировка с подсчётом частот ключей.

decreaseKey

Decrease key

Уменьшение ключа известного узла.

DSU / СНМ

Disjoint-set union

Структура, поддерживающая разбиение элементов на попарно непересекающиеся множества и операции find и union.

Feasibility check

Проверка допустимости

Ответ, достижимо ли решение при фиксированном параметре.

FIFO

First in, first out

Первым добавлен — первым извлечён.

find

Find

Возвращает представитель класса элемента.

getMin

Find minimum

Чтение минимального элемента без удаления.

Heapify

Heap construction

Перестройка массива в кучу; снизу вверх выполняется за O(n).

Heapsort

Heap sort

Сортировка с помощью кучи за Θ(n log n).

LIFO

Last in, first out

Последним добавлен — первым извлечён.

LSD

Least significant digit

Порядок разрядов от младшего к старшему.

makeSet

Make set

Создаёт одноэлементное множество.

Max-куча

Max-heap

У каждого родителя значение ≥ значениям детей.

meld

Meld

Объединение двух куч.

Min-куча

Min-heap

У каждого родителя значение ≤ значениям детей.

Partition

Partition

Перестройка по отношению к опорному элементу.

Path compression

Сжатие пути

Перенаправление посещённых ссылок к корню.

Pivot

Pivot

Опорный элемент разбиения.

Pointer machine

Pointer machine

Модель узлов с прямым доступом через ссылки.

QuickSelect

Selection algorithm

Поиск одного элемента заданного ранга.

QuickSort

Quick sort

Рекурсивная сортировка разбиением.

Radix sort

Radix sort

Последовательная устойчивая сортировка по цифрам ключа.

RAM-модель

Random Access Machine

Идеализированная модель, в которой доступ к ячейке памяти по адресу занимает одну операцию.

Абстракция памяти с доступом по адресу за O(1).

removeMin

Extract minimum

Также: extractMin

Удаление одного вхождения минимума.

Извлечь и удалить минимальный элемент.

Top-down

Сверху вниз

Вычисление состояний по рекурсивному запросу.

union

Union

Объединяет два класса.

Upper bound

Upper bound

Первый индекс i с A[i]>x.