Определения

0-1 BFS: 0-1 BFS — это обход графа с весами рёбер 0 и 1, где переход веса 0 кладёт вершину в начало дека, а переход веса 1 — в конец.
АЛГОРИТМ: Алгоритм — это конечное описание шагов, которое преобразует допустимый вход в выход.
АМОРТИЗИРОВАННАЯ СЛОЖНОСТЬ: Амортизированная сложность — это оценка средней стоимости операции в худшем случае для всей последовательности операций, а не вероятностное среднее по случайным входам.
ВЕРХУШКА СТЕКА: Верхушка стека — это единственный элемент, который можно прочитать или снять напрямую.
ВМЕСТИМОСТЬ ДИНАМИЧЕСКОГО МАССИВА: Вместимость динамического массива — это количество элементов, которое текущий буфер может вместить без нового выделения памяти.
ВМЕСТИМОСТЬ ОЧЕРЕДИ: Вместимость очереди — это длина фиксированного буфера, которую структура не увеличивает автоматически.
ВРЕМЕННАЯ СЛОЖНОСТЬ: Временная сложность — это функция, которая оценивает количество элементарных операций алгоритма в зависимости от размера входа.
ДВУМЕРНАЯ РАЗРЕЖЕННАЯ ТАБЛИЦА: Двумерная разреженная таблица — это структура данных для статической матрицы, которая заранее хранит ответы для прямоугольных блоков размера 2^kr x 2^kc.
ДВУСВЯЗНЫЙ СПИСОК: Двусвязный список — это структура данных, которая хранит элементы в узлах, где каждый узел содержит значение, ссылку prev на предыдущий узел и ссылку next на следующий узел.
ДВУСТОРОННЯЯ ОЧЕРЕДЬ: Двусторонняя очередь — это очередь, у которой начало и конец являются рабочими сторонами.
ДЕК: Дек — это структура данных, которая добавляет и удаляет элементы с обоих концов.
ДИНАМИЧЕСКИЙ МАССИВ: Динамический массив — это структура данных, которая хранит элементы в непрерывном буфере, поддерживает быстрый доступ по индексу и увеличивает вместимость при необходимости.
ЗАДАЧА АЛГОРИТМА: Задача алгоритма — это описание допустимых входов, требуемых выходов и условия, которое связывает каждый правильный выход с соответствующим входом.
ЗАКРЫТАЯ АДРЕСАЦИЯ: Закрытая адресация в этой статье хранит в каждой ячейке массива бакет с динамическим массивом записей key/value.
ЗАПРОС НА ОТРЕЗКЕ: Запрос на отрезке — это вопрос о значениях массива между двумя заданными границами.
ЗАПРОС ПО ГИПЕРПРЯМОУГОЛЬНИКУ: Запрос по гиперпрямоугольнику — это k-мерный запрос, где по каждому измерению задается свой полуоткрытый диапазон.
ЗАПРОС ЧЕРЕЗ ПЕРЕКРЫВАЮЩИЕСЯ БЛОКИ: Запрос через перекрывающиеся блоки — это способ ответить на отрезке двумя блоками одинаковой степенной длины, которые вместе покрывают запрос.
ЗАПРОС ЧЕРЕЗ ПЕРЕКРЫВАЮЩИЕСЯ БЛОКИ: Многомерный запрос через перекрывающиеся блоки объединяет угловые блоки запроса; повторное покрытие клеток корректно только для идемпотентной операции.
ЗАЦИКЛИВАНИЕ ИНДЕКСА: Зацикливание индекса — это переход от последней ячейки массива к первой по формуле (index + 1) % capacity.
ИДЕМПОТЕНТНАЯ ОПЕРАЦИЯ: Идемпотентная операция — это операция, для которой повтор одного значения не меняет результат: op(x, x) = x.
ИДЕМПОТЕНТНАЯ ОПЕРАЦИЯ: Идемпотентная операция в многомерной sparse table позволяет безопасно объединять перекрывающиеся блоки, потому что op(x, x) = x.
ИНВАРИАНТ ЦИКЛА: Инвариант цикла — это утверждение, которое истинно перед началом цикла и остается истинным после каждой итерации.
ИНДЕКС HEAD: Индекс head указывает на первый логический элемент очереди, если size больше 0.
ИНДЕКС TAIL: Индекс tail указывает на следующую свободную позицию для записи, а не на последний элемент.
КВАДРАТИЧНОЕ ПРОБИРОВАНИЕ: Квадратичное пробирование строит следующую попытку по формуле index_i = (h + c1 * i + c2 * i * i) mod capacity.
КОЛЛИЗИЯ ХЕША: Коллизия хеша возникает, когда разные ключи приводят к одному индексу таблицы.
КОЛЬЦЕВАЯ ОЧЕРЕДЬ: Кольцевая очередь — это FIFO-очередь фиксированной вместимости, которая хранит элементы в массиве и переиспользует свободные ячейки по кругу.
КОЛЬЦЕВОЙ БУФЕР: Кольцевой буфер — это массив, где следующий индекс после последней ячейки снова становится индексом 0.
КОНЕЦ ДЕКА: Конец дека — это сторона, где работают операции push_back, pop_back и back.
КОНЕЦ ОЧЕРЕДИ: Конец очереди — это сторона очереди, куда добавляют новый элемент.
МНОГОМЕРНАЯ РАЗРЕЖЕННАЯ ТАБЛИЦА: Многомерная разреженная таблица — это обобщение sparse table на k измерений, где блок задается вектором степенных размеров по всем осям.
МНОЖЕСТВО К статье: Множество в математическом анализе — это совокупность уникальных элементов, которые могут быть числами, символами или другими объектами.
МОНОТОННЫЙ ДЕК: Монотонный дек — это дек с дополнительным порядком элементов, который помогает читать минимум или максимум окна с края.
НАЧАЛО ДЕКА: Начало дека — это сторона, где работают операции push_front, pop_front и front.
НАЧАЛО ОЧЕРЕДИ: Начало очереди — это сторона очереди, откуда читают или удаляют следующий элемент.
НЕПЕРЕСЕКАЮЩИЕСЯ МНОЖЕСТВА К статье: Непересекающиеся множества — это множества, которые не имеют общих элементов.
О-МАЛОЕ: о-малое задает строгую верхнюю оценку: f(n) = o(g(n)), если отношение f(n) к g(n) стремится к нулю.
ОБЪЕДИНЕНИЕ МНОЖЕСТВ К статье: Объединение множеств — это множество, содержащее все элементы из обоих множеств.
ОДНОСВЯЗНЫЙ СПИСОК: Односвязный список — это структура данных, которая хранит элементы в узлах, где каждый узел содержит значение и ссылку next на следующий узел цепочки.
ОМЕГА-МАЛОЕ: омега-малое задает строгую нижнюю оценку: f(n) = ω(g(n)), если отношение f(n) к g(n) стремится к бесконечности.
ОПУСТОШЕНИЕ: Опустошение — это попытка удалить или прочитать элемент, когда size равен 0.
ОТКРЫТАЯ АДРЕСАЦИЯ: Открытая адресация хранит записи прямо в массиве слотов и при коллизии ищет другой слот по probe-последовательности.
ОЧЕРЕДЬ: Очередь — это структура данных, где первый добавленный элемент извлекается первым.
ПЕРЕПОЛНЕНИЕ: Переполнение — это попытка добавить элемент, когда size равен capacity.
ПЕРЕСЕЧЕНИЕ МНОЖЕСТВ К статье: Пересечение множеств — это множество, содержащее только те элементы, которые принадлежат обоим множествам.
ПЕРЕХЕШИРОВАНИЕ: Перехеширование — это перенос записей в таблицу другой вместимости с повторным вычислением индексов.
ПОДМНОЖЕСТВО К статье: Подмножество — это множество, все элементы которого также являются элементами другого множества.
ПОЛНАЯ КОРРЕКТНОСТЬ: Полная корректность означает частичную корректность вместе с терминальностью.
ПОЛУОТКРЫТЫЙ ДИАПАЗОН: Полуоткрытый диапазон включает левую границу и не включает правую, поэтому его длина равна разности правой и левой границ.
ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ: Пространственная сложность — это функция, которая оценивает дополнительную память алгоритма в зависимости от размера входа.
ПРЯМОУГОЛЬНЫЙ ЗАПРОС: Прямоугольный запрос — это запрос ко всем клеткам матрицы внутри произведения двух диапазонов по строкам и столбцам.
ПУСТОЕ МНОЖЕСТВО К статье: Пустое множество — это множество, не содержащее ни одного элемента.
РАВЕНСТВО МНОЖЕСТВ К статье: Два множества равны, если они содержат одни и те же элементы.
РАЗМЕР ДИНАМИЧЕСКОГО МАССИВА: Размер динамического массива — это количество элементов, доступных пользователю.
РАЗНОСТЬ МНОЖЕСТВ К статье: Разность множеств A и B — это множество, содержащее элементы, которые принадлежат A, но не принадлежат B.
РАЗРЕЖЕННАЯ ТАБЛИЦА: Разреженная таблица — это структура данных для статического массива, которая заранее хранит ответы на блоках степенной длины.
РЕКУРРЕНТНОЕ СООТНОШЕНИЕ: Рекуррентное соотношение — это формула, которая выражает стоимость задачи через стоимость меньших задач того же вида и работу вне этих подзадач.
СОБСТВЕННОЕ ПОДМНОЖЕСТВО К статье: Собственное подмножество — это подмножество, которое не равно исходному множеству, то есть содержит меньше элементов.
ССЫЛКА NEXT: Ссылка next — это поле узла, которое указывает на следующий узел или на пустую ссылку, если узел последний.
ССЫЛКА NEXT: Ссылка next — это поле узла, которое указывает на следующий узел или на пустую ссылку, если узел последний.
ССЫЛКА PREV: Ссылка prev — это поле узла, которое указывает на предыдущий узел или на пустую ссылку, если узел первый.
СТЕК: Стек — это структура данных, где последний добавленный элемент извлекается первым.
ТЕРМИНАЛЬНОСТЬ: Терминальность означает: алгоритм завершает работу на каждом допустимом входе.
УЗЕЛ ДВУСВЯЗНОГО СПИСКА: Узел двусвязного списка — это объект или структура, которая хранит значение value, ссылку prev на предыдущий узел и ссылку next на следующий узел.
УЗЕЛ СПИСКА: Узел списка — это объект или структура, которая хранит пользовательское значение и ссылку на следующий узел.
ХЕШ-ТАБЛИЦА: Хеш-таблица — это структура данных для хранения пар key/value, где поиск, вставка и удаление идут по маршруту, построенному из ключа.
ХЕШ-ФУНКЦИЯ: Хеш-функция превращает строковый ключ в число, из которого затем получают индекс массива.
ЧАСТИЧНАЯ КОРРЕКТНОСТЬ: Частичная корректность означает: если алгоритм завершился на допустимом входе, то его результат удовлетворяет постусловию задачи.
DEQUEUE: dequeue — это операция, которая удаляет и возвращает элемент из начала очереди.
DEQUEUE: dequeue в кольцевой очереди — это операция, которая читает элемент из head, удаляет его из логической очереди и переносит head вперёд.
ENQUEUE: enqueue — это операция, которая добавляет новый элемент в конец очереди.
ENQUEUE: enqueue в кольцевой очереди — это операция, которая записывает новый элемент в tail и переносит tail на следующую позицию записи.
FIFO: FIFO — это правило first in, first out: первый добавленный элемент извлекается первым.
FNV-1A: FNV-1a — это детерминированная учебная хеш-функция, которая в этой статье используется для строковых ключей.
HEAD: head — это ссылка на первый узел списка.
HEAD: head — это ссылка на первый пользовательский узел цепочки.
LIFO: LIFO — это правило last in, first out: последний добавленный элемент извлекается первым.
LOAD FACTOR: Load factor показывает заполненность хеш-таблицы и используется как сигнал для resize или rehash.
O-НОТАЦИЯ: O-нотация задает асимптотическую верхнюю оценку: f(n) = O(g(n)), если начиная с некоторого места f(n) не превосходит константу, умноженную на g(n).
PEEK: peek — это операция, которая читает верхний элемент стека без удаления.
PEEK: peek — это операция, которая читает начало очереди без удаления.
POP: pop — это операция, которая удаляет и возвращает верхний элемент стека.
POP_BACK: pop_back — это операция, которая удаляет и возвращает элемент из конца дека.
POP_FRONT: pop_front — это операция, которая удаляет и возвращает элемент из начала дека.
PUSH: push — это операция, которая добавляет новый элемент на верхушку стека.
PUSH_BACK: push_back — это операция, которая добавляет новый элемент в конец дека.
PUSH_FRONT: push_front — это операция, которая добавляет новый элемент в начало дека.
RESIZE: Resize — это операция замены текущего буфера на буфер другой вместимости с сохранением активных элементов.
RMQ: RMQ — это запрос минимума на отрезке массива.
SENTINEL-УЗЕЛ: Sentinel-узел — это фиктивный узел, который участвует в ссылках списка, но не является пользовательским элементом.
TAIL: tail — это ссылка на последний узел списка, если реализация хранит хвост для быстрого добавления в конец.
TAIL: tail — это ссылка на последний пользовательский узел цепочки.
TOMBSTONE-СЛОТ: Tombstone-слот — это удалённый слот открытой адресации, который не хранит запись, но не останавливает поиск.
Θ-НОТАЦИЯ: Θ-нотация задает точную асимптотическую оценку с точностью до констант: f(n) = Θ(g(n)), если одновременно f(n) = O(g(n)) и f(n) = Ω(g(n)).
Ω-НОТАЦИЯ: Ω-нотация задает асимптотическую нижнюю оценку: f(n) = Ω(g(n)), если начиная с некоторого места f(n) не меньше константы, умноженной на g(n).