Это ужасно! Я попытался собрать всю нужную информацию и ссылки в один файлик. Надеюсь, это будет хоть сколько-нибудь полезно. За точность не отвечаю, хотя я и пытался проверять. Были использованы следующие материалы и инструменты: чей-то украденный конспект (спасибо огромное этому человеку), информация из книги Кормена, старый файлик с ответами, Gemini-1.5-Pro.
Плейлист на YouTube с записями (почти) всех лекций 2024 года: https://www.youtube.com/playlist?list=PL8bFx8PltE4MSAk_SaW_MSnpVO91Cw-a1. Ссылки на видео с лекций ниже приведены с учетом таймкодов (но я это не доделал).
Книга Кормена c поиском: https://disk.yandex.ru/d/6PhppDCEL-5M0g
Задания с ответами в самом конце!!!
Перед использованием просьба провести фактчекинг :)
PDF-версия: ADS.pdf; исходник на markdown: АСД.md
Основы анализа алгоритмов. Асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации; эмпирические измерения эффективности алгоритмов; накладные расходы алгоритмов по времени и памяти.
Рекуррентные соотношения и анализ рекурсивных алгоритмов. Определение, методы подстановки, итераций, деревья рекурсии. Основная теорема о рекуррентных соотношениях.
Динамические структуры данных. Линейные списки. Деревья: двоичные, деревья поиска, ветвящиеся деревья. Способы представления. Сбалансированные деревья: AVL-деревья, B-деревья, Красно-черные деревья, идеально сбалансированное дерево. Сравнение стоимости операций – асимптотические и эмпирические оценки.
Амортизационный анализ. (Помнить, зачем это надо). Учётные стоимости операций, использование при оценке времени работы алгоритмов. Методы группировки, предоплаты, потенциалов. Требования к потенциальной функции. Системы непересекающихся множеств. Основные операции, оценка амортизированной стоимости операций.
Графы. Представление графов – матрица смежности, списки смежности. Стратегии поиска в ширину, в глубину. Алгоритмы Дейкстры, Крускала, Прима. Топологическая сортировка. Алгоритм поиска сильно связных компонент.
Хэш-функции, хэш-таблицы. Открытая адресация, таблицы на основе цепочек. Базовые виды хеш-функций. Проблемы кластеризации, удаления элементов. Реализация структуры данных «словарь» на основе хэш-таблицы. Хопскотч, Робин-Гуд, двухвыборное (не то же, что и двойное!!), кукушкино хеширование.
Кучи. Двоичные кучи, сортировка с помощью двоичной кучи, оценка эффективности.
Стратегии переборных алгоритмов. Полный перебор, метод ветвей и границ на примере задачи коммивояжера.
Динамическое программирование. Признаки применимости, общая стратегия. Стратегии «сверху вниз» (используя механизм мемоизации) и «снизу вверх». Алгоритм перемножения матриц, поиск наибольшей общей подпоследовательности, задача о рюкзаке.
Жадные алгоритмы. Признаки применимости жадных алгоритмов, задача о рюкзаке (непрерывный варианты).
Алгоритмы поиска подстрок. «Наивный» алгоритм, алгоритмы РабинаКарпа, Кнута-Морриса-Пратта, Бойера-Мура (общая идея). Поиск подстрок с помощью конечных автоматов.
Примечания: в алгоритмах знать оценки, сильные слабые стороны, при каких сценариях выгоднее; + биноминальные деревья и кучи, фиббоначиевы (представление о них) + сортировка подсчётом.
Анализ алгоритмов — это процесс определения количества ресурсов, необходимых для выполнения алгоритма. Обычно оценивается время выполнения, но также могут быть рассмотрены и другие ресурсы, такие как память, пропускная способность сети или необходимое аппаратное обеспечение.
Асимптотический анализ фокусируется на поведении алгоритма при увеличении размера входных данных до бесконечности. Он позволяет абстрагироваться от деталей реализации и аппаратного обеспечения, сосредоточившись на порядке роста времени выполнения.
Наилучший случай: Минимальное время выполнения для входных данных определенного размера. Например, для сортировки вставкой наилучший случай - это уже отсортированный массив.
Наихудший случай: Максимальное время выполнения для входных данных определенного размера. Для сортировки вставкой наихудший случай - это массив, отсортированный в обратном порядке.
Средний случай: Среднее время выполнения по всем возможным входным данным определенного размера. Для анализа среднего случая необходимо знать распределение входных данных, что не всегда возможно.
Наилучший случай часто неинформативен, так как редко встречается на практике.
Наихудший случай гарантирует, что алгоритм не будет работать дольше определенного времени, но может быть пессимистичным.
Средний случай более реалистичен, но его анализ сложнее и требует знания о распределении входных данных.
В лекциях: https://youtu.be/Ju2tp7S-jfc?si=ZrUFi4eUqWcCT_Jd&t=1594
Нотация Бахмана–Ландау:
O-нотация (О-большое): Дает верхнюю границу времени выполнения. Запись
Ω-нотация (Омега-большое): Дает нижнюю границу времени выполнения. Запись
Θ-нотация (Тета-большое): Дает асимптотически точную оценку времени выполнения. Запись
o-нотация (о-малое): Указывает, что функция
ω-нотация (омега-малое): Указывает, что функция
Замечания!
Любой логарифм растет медленнее степенной функции
Любая степенная функция растет медленнее показательной
Основание логарифмов не важно, т.к. скорость роста одинаковая с точностью до
Асимптотический анализ дает теоретическую оценку времени выполнения, но на практике важно проводить эмпирические измерения. Для этого алгоритм реализуется в виде программы и запускается на реальном компьютере с различными наборами входных данных. Измеряется фактическое время выполнения, которое затем сопоставляется с теоретическими оценками.
При анализе алгоритма важно учитывать накладные расходы (overhead), связанные с его реализацией. Например, рекурсивный алгоритм может иметь большие накладные расходы, связанные с вызовами функций.
Включают в себя время, затрачиваемое на выполнение вспомогательных операций, таких как:
Вызовы функций
Выделение и освобождение памяти
Проверка условий
Обновление счетчиков
Включают в себя память, используемую для хранения:
Локальных переменных
Параметров функций
Вспомогательных структур данных
Время работы алгоритма.
В лучшем случае:
В худшем случае:
Рекуррентные соотношения (recurrence relations) — это уравнения, определяющие последовательность чисел, в которых каждый член последовательности выражается через предыдущие члены. Они часто используются для анализа времени работы рекурсивных алгоритмов, поскольку естественным образом описывают, как время работы задачи размером
Рекуррентное соотношение — это соотношение вида:
Например, рекуррентное соотношение для времени работы алгоритма сортировки слиянием имеет вид:
Существует несколько методов решения рекуррентных соотношений, т.е. получения асимптотических границ для
В методе подстановки (substitution method) мы делаем предположение о виде решения, а затем используем математическую индукцию для доказательства его корректности.
В методе итераций (iteration method) мы многократно подставляем рекуррентное уравнение в само себя, раскрывая рекурсию до тех пор, пока не получим выражение, не содержащее рекурсивных вызовов.
Раскрытие рекурсии: Подставляем рекуррентное уравнение в само себя, заменяя
Упрощение: Упрощаем полученное выражение, объединяя подобные члены.
Поиск закономерности: Ищем закономерность в полученных выражениях и обобщаем её для произвольного уровня рекурсии.
Вычисление суммы: Вычисляем сумму, полученную в результате раскрытия рекурсии.
тут скорее всего должно быть что-то еще
Дерево рекурсии (recursion tree) — это графическое представление рекурсивных вызовов алгоритма. Каждый узел дерева представляет один рекурсивный вызов, а ребра соединяют вызовы, связанные отношением "родитель-потомок". Стоимость каждого узла — это время работы соответствующего рекурсивного вызова, не включая время, затрачиваемое на рекурсивные вызовы, которые он выполняет.
Построение дерева: Строим дерево рекурсии, начиная с корня, представляющего исходный вызов алгоритма.
Оценка стоимости уровней: Оцениваем стоимость каждого уровня дерева, суммируя стоимости всех узлов на этом уровне.
Вычисление общей стоимости: Суммируем стоимости всех уровней дерева, чтобы получить общую стоимость вычисления.
Основная теорема (master theorem) предоставляет "кулинарную книгу" для решения рекуррентных соотношений вида:
где
Основная теорема гласит следующее:
Если
Если
Если
Замечание!
Рассмотрим рекуррентное соотношение для сортировки слиянием:
Здесь
Вычислим
Поскольку
Следовательно,
Рассмотрим рекуррентное соотношение:
Здесь
Вычислим
Поскольку
Поскольку
Динамические структуры данных — это структуры данных, которые могут изменяться во время выполнения программы: элементы могут добавляться, удаляться или изменяться. Это отличает их от статических структур данных, таких как массивы, размер которых фиксирован.
Линейные списки — это структуры данных, в которых элементы упорядочены линейно. Каждый элемент содержит данные и ссылку на следующий элемент списка.
Односвязный список: Каждый элемент содержит ссылку только на следующий элемент.
Двусвязный список: Каждый элемент содержит ссылки на предыдущий и следующий элементы.
Циклический список: Последний элемент списка ссылается на первый.
Операция | Односвязный список | Двусвязный список |
---|---|---|
Вставка в начало | O(1) | O(1) |
Вставка в конец | O(n) | O(1) |
Удаление | O(n) | O(1) |
Поиск | O(n) | O(n) |
Алгоритм поиска
xxxxxxxxxx
41x = L.head
2while x != NIL and x.key != k
3 x = x.next
4return x
Вставка в двусвязный список (в начало)
xxxxxxxxxx
51x.next = L.head
2if L.head != NIL:
3 L.head.prev = x
4L.head = x
5x.prev = NIL
Вставка в односвязный список (в начало)
xxxxxxxxxx
21x.next = L.head
2L.head = x
Вставка в конец односвязного списка
xxxxxxxxxx
101function appendToEnd(L, x):
2 if L.head == null:
3 L.head = x
4 x.next = null
5 else:
6 current = L.head
7 while current.next != null:
8 current = current.next
9 current.next = x
10 x.next = null
Вставка в конец двусвязного списка
xxxxxxxxxx
121function appendToEnd(L, x):
2 if L.head == null:
3 L.head = x
4 x.next = null
5 x.prev = null
6 else:
7 current = L.head
8 while current.next != null:
9 current = current.next
10 current.next = x
11 x.prev = current
12 x.next = null
Удаление из односвязного списка
xxxxxxxxxx
111function deleteNode(L, value):
2 if L.head == null:
3 return // список пуст
4 if L.head.value == value:
5 L.head = L.head.next
6 return
7 current = L.head
8 while current.next != null and current.next.value != value:
9 current = current.next
10 if current.next != null:
11 current.next = current.next.next
Удаление из двусвязного списка
xxxxxxxxxx
161function deleteNode(L, value):
2 if L.head == null:
3 return // список пуст
4 if L.head.value == value:
5 L.head = L.head.next
6 if L.head != null:
7 L.head.prev = null
8 return
9 current = L.head
10 while current != null and current.value != value:
11 current = current.next
12 if current != null:
13 if current.next != null:
14 current.next.prev = current.prev
15 if current.prev != null:
16 current.prev.next = current.next
Деревья — это нелинейные структуры данных, в которых элементы организованы иерархически. Каждый элемент называется узлом, а связи между узлами — ребрами.
В deque
: каждый элемент знает только своего родителя.
В обычном массиве. Родитель
С помощью узлов. Стоимость доступа
Двоичное дерево — это дерево, в котором каждый узел имеет не более двух дочерних узлов.
Дерево поиска — это двоичное дерево, в котором для каждого узла x выполняется следующее свойство: все ключи в левом поддереве x меньше x.key, а все ключи в правом поддереве x больше x.key.
Замечания!
В std используется операция «меньше», элементы должны определять ее.
Если дерево может содержать дубликаты, обычно не используется поиск по значению. Можно использовать инфиксный обход:
Элементы по порядку записи в массиве:
xxxxxxxxxx
21[--] [--] [17] [17] [17] [17] [20]
2^ lower ^ upper
lower_bound
— первый элемент, больший либо равный x
upper_bound
— первый элемент, больший x
Тогда в диапазоне от lower_bound до upper_bound будут располагаться все дубликаты.
Вставка
Извлечение (поиск)
Следующий
Предыдущий
Минимальный
Максимальный
Note
Чтобы элементы могли находиться в set
(и прочем подобном), необходимо, чтобы на этих элементах была определена операция «меньше». set
может также работать с компаратором «больше», но не «меньше либо равно», «больше либо равно».
Введем на произвольном множестве бинарное отношение:
Если это отношение позволяет различать все элементы множества, то это полный порядок.
Weak ordering (слабый порядок) – бинарное отношение на элементах множества, при котором некоторые элементы множества не различаются между собой. Пример: «количество цифр в x, больше, чем в y».
Note
Weak ordering не используется в структурах по типу set — необходимо более строгое ограничение. multiset
позволяет поддерживать неполный порядок.
Strict weak ordering (отношение строго частичного порядка) — бинарное отношение на элементах множества со следующими свойствами:
Irreflexivity:
Assymetry:
Transitivity:
Несравнимость:
Замечание.
Ветвящееся дерево — это дерево, в котором каждый узел может иметь произвольное количество дочерних узлов.
Этот способ часто используется для представления полных бинарных деревьев, таких как пирамиды (heaps). В таком представлении:
Корень дерева находится в позиции 0.
Для узла на позиции
Левый потомок находится на позиции
Правый потомок находится на позиции
Родительский узел находится на позиции
Пример
Рассмотрим полное бинарное дерево:
Его представление в массиве будет:
xxxxxxxxxx
11[10, 15, 30, 40, 50, 100, 40]
Этот способ используется для представления произвольных деревьев, в которых каждый узел содержит указатели на своих дочерних узлов. В бинарном дереве каждый узел имеет два указателя: на левого и правого потомка.
Пример
Рассмотрим бинарное дерево:
Каждый узел будет представляться структурой:
xxxxxxxxxx
51Node {
2 value: int
3 left: Node
4 right: Node
5}
И представление дерева будет выглядеть так:
xxxxxxxxxx
41root = Node(10)
2root.left = Node(15)
3root.right = Node(30)
4root.left.left = Node(40)
Этот способ используется для представления ветвящихся деревьев, где узлы могут иметь произвольное количество потомков. Каждый узел имеет два указателя: на своего первого (левого) потомка и на следующего (правого) брата.
Пример
Рассмотрим дерево:
Каждый узел будет представляться структурой:
xxxxxxxxxx
51Node {
2 value: int
3 leftChild: Node
4 rightSibling: Node
5}
И представление дерева будет выглядеть так:
xxxxxxxxxx
61root = Node(1)
2root.leftChild = Node(2)
3root.leftChild.rightSibling = Node(3)
4root.leftChild.rightSibling.rightSibling = Node(4)
5root.leftChild.leftChild = Node(5)
6root.leftChild.leftChild.rightSibling = Node(6)
В этом представлении:
Узел 1 имеет левого потомка 2 и правого брата 3.
Узел 2 имеет левого потомка 5 и правого брата 6.
Узел 3 является правым братом узла 2.
Узел 4 является правым братом узла 3.
Таким образом, указанный способ позволяет эффективно представлять деревья с произвольным числом потомков для каждого узла.
[Более строгое определение] Сбалансированное дерево — это дерево поиска, в котором для любого узла количество элементов в левом и правом поддереве различается не более, чем на 1.
[Менее строгое определение] Дерево называется сбалансированным, если для любого узла
При вставке или удалении требуется перестроение дерева. Таким образом,
RB-tree — частный случай B-tree.
Красно-черное дерево представляет собой бинарное дерево поиска с одним дополнительным битом цвета в каждом узле. Цвет узла может быть либо красным (
Каждый узел дерева содержит атрибуты
Бинарное дерево поиска является красно-черным деревом, если оно удовлетворяет следующим красно-черным свойствам.
Important
Каждый узел является либо красным, либо черным.
Корень дерева является черным узлом.
Каждый лист дерева (NIL) является черным узлом.
Если узел красный, то оба его дочерних узла черные.
Для каждого узла все простые пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов.
Замечание. Можно обойтись без затрат на цвет, но обычно это не окупается. В худшем случае возможно не более, чем 2-кратное различие по высотам поддеревьев.
Important
Лемма. Красно-черное дерево с
Следствие. Такие операции над динамическими множествами, как
О вставке ниже.
Правое вращение.
xxxxxxxxxx
141Right-Rotate(T, x)
2 y = x.left
3 x.left = y.right
4 if y.right != T.nil
5 y.right.p = x
6 y.p = x.p
7 if x.p == T.nil
8 T.root = y
9 elseif x == x.p.left
10 x.p.left = y
11 else
12 x.p.right = y
13 y. right = x
14 x.p = y
Вставляем всегда красный элемент (для сохранения баланса). Но можем получить тогда «локальную проблему» – 2 подряд идущих красных узла. В таком случае, нужно восстановить красно-черные свойства.
В RB-tree вводится вспомогательная операция вращения (выше).
Черная высота узла (black height) — количество черных вершин в пути от узла к листу, не считая сам лист (цвет вершины, от которой идем, нас не интересует).
Лемма 1. В пути от вершины с черной высотой
Лемма 2. КЧД с
Получается, что высота КЧД превосходит высоту идеально сбалансированного дерева не более, чем в 2 раза. Причем при больших
Таким образом, получили, что у всех операций АС
AVL-деревья, названные в честь своих создателей, Адельсона-Вельского и Ландиса, представляют собой самобалансирующиеся бинарные деревья поиска. Они гарантируют логарифмическую сложность основных операций (вставка, удаление, поиск) даже в худшем случае, предотвращая вырождение дерева в линейный список.
Свойство бинарного дерева поиска: Для каждого узла все ключи в левом поддереве меньше ключа узла, а все ключи в правом поддереве больше.
Свойство балансировки: Для каждого узла разница высот его левого и правого поддеревьев (называемая баланс-фактором) не превышает 1 (может быть -1, 0 или 1).
Высота дерева
При вставке или удалении узла баланс дерева может нарушиться. Для восстановления баланса AVL-деревья используют повороты:
Левый поворот: применяется, когда баланс-фактор узла становится равным -2, а баланс-фактор его правого потомка -1 или 0.
Правый поворот: применяется, когда баланс-фактор узла становится равным 2, а баланс-фактор его левого потомка 1 или 0.
Двойной поворот (лево-правый или право-левый): применяется в остальных случаях нарушения баланса.
Для реализации каждая вершина имеет дополнительное поле — высота данного узла.
Вставка
Вставка нового узла происходит как в обычном бинарном дереве поиска.
После вставки проверяется баланс-фактор каждого узла на пути от нового узла до корня.
При нарушении баланса выполняется соответствующий поворот.
Требует 2 вращения.
Удаление
Удаление узла происходит как в обычном бинарном дереве поиска.
После удаления проверяется баланс-фактор каждого узла на пути от родителя удаленного узла до корня.
При нарушении баланса выполняется соответствующий поворот.
Может потребовать вращений в количестве высоты дерева (медленнее, чем КЧД).
Поиск
Поиск ключа происходит как в обычном бинарном дереве поиска.
Быстрее поиска в КЧД.
При построении случайных AVL-деревьев, наиболее велика вероятность получить идеальное.
Операция | AVL-дерево | Бинарное дерево поиска | Красно-черное дерево | B-дерево |
---|---|---|---|---|
Вставка | O(log n) | O(n) | O(log n) | O(log n) |
Удаление | O(log n) | O(n) | O(log n) | O(log n) |
Поиск | O(log n) | O(n) | O(log n) | O(log n) |
Гарантированная логарифмическая сложность операций.
Простота реализации поворотов.
Большое количество поворотов при частых вставках и удалениях.
Небольшая разница в производительности по сравнению с красно-черными деревьями, которые требуют меньше поворотов.
set, multiset, map, multimap – обычно КЧД
Технически, неважно, какой элемент, главное – наличие сравнения
Итератор – bidirectional и совпадает с константным
Операции не перемещают элементы в памяти
Allocator – некий объект, сущность которого используется для выделения и освобождения памяти. Allocator = распределитель памяти.
Сложность при создании map / set из диапазона:
иначе
B-деревья, в отличие от AVL-деревьев и красно-черных деревьев, оптимизированы для хранения данных на внешних носителях, таких как жесткие диски. Они отличаются от бинарных деревьев поиска тем, что каждый узел может содержать несколько ключей и указателей на дочерние узлы.
Упорядоченность ключей: Ключи в каждом узле хранятся в отсортированном (неубывающем) порядке.
Количество ключей: Каждый узел, кроме корня, содержит от
Количество потомков: Каждый узел имеет на один потомок больше, чем ключей.
Сбалансированность: Все листья находятся на одной глубине.
Высота. Для любого дерева с
Асимптотика
Поиск:
Поиск ключа начинается с корня.
В каждом узле выполняется поиск ключа среди ключей узла.
Если ключ найден, поиск завершается.
Если ключ не найден, поиск продолжается в соответствующем поддереве.
Вставка:
Новый ключ вставляется в соответствующий лист.
Если лист переполнен (содержит
Средний ключ из переполненного листа перемещается в родительский узел.
Если родительский узел переполнен, он также разбивается, и этот процесс продолжается вверх по дереву до корня.
Если корень переполнен, создается новый корень, и высота дерева увеличивается на 1.
Удаление:
Удаление ключа происходит из соответствующего узла.
Если узел становится недополненным (содержит меньше t ключей), он объединяется с соседним узлом.
Если соседний узел также не дополнен, объединение происходит с родительским узлом, и этот процесс продолжается вниз по дереву до листьев.
Оптимизация для дискового хранения: B-деревья минимизируют количество операций чтения с диска, поскольку каждый узел содержит много ключей.
Сбалансированность: B-деревья гарантируют логарифмическую сложность операций.
Сложность реализации: B-деревья сложнее в реализации, чем бинарные деревья поиска.
B-деревья, как и AVL-деревья и красно-черные деревья, обеспечивают логарифмическую сложность операций. Однако B-деревья оптимизированы для дискового хранения, а AVL-деревья и красно-черные деревья - для оперативной памяти.
Базы данных: B-деревья широко используются в системах управления базами данных для индексирования данных.
Файловые системы: B-деревья используются в некоторых файловых системах для организации данных на диске.
Идеально сбалансированное дерево — это дерево, в котором все листья находятся на одной глубине.
Операция | Двоичное дерево поиска (наихудший случай) | Сбалансированное дерево поиска |
---|---|---|
Вставка | O(n) | O(log n) |
Удаление | O(n) | O(log n) |
Поиск | O(n) | O(log n) |
Минимум | O(n) | O(log n) |
Максимум | O(n) | O(log n) |
Преемник | O(n) | O(log n) |
Предшественник | O(n) | O(log n) |
И еще неплохая табличка, украденная из чьего-то конспекта.
Поиск | Insert, beg | I, mid | I, end | Доступ [] | Издержки | ||
---|---|---|---|---|---|---|---|
Массив | vector, array, deque | ||||||
list, forward list | |||||||
RBT | set, multiset, map, multimap | 3 | |||||
Hash-table | unordered_set, unordered_map |
Замечание. Издержки – на хранение одного элемента.
На практике сбалансированные деревья поиска (например, красно-черные деревья) обычно работают быстрее, чем несбалансированные деревья поиска, даже для небольших наборов данных.
Амортизационный анализ — это метод анализа алгоритмов, который позволяет оценить среднее время выполнения операции в последовательности операций. Он особенно полезен, когда в последовательности встречаются как "дешевые", так и "дорогие" операции, и важно понять, как "дорогие" операции влияют на общую производительность.
Зачем нужен амортизационный анализ?
Более точная оценка: Амортизационный анализ позволяет получить более точную оценку времени работы алгоритма, чем анализ наихудшего случая для каждой операции.
Учет редких операций: Он позволяет учесть влияние редких, но "дорогих" операций, которые могут существенно исказить оценку времени работы в наихудшем случае.
Анализ структур данных: Амортизационный анализ широко используется для анализа эффективности операций в динамических структурах данных, таких как динамические массивы, деревья поиска и системы непересекающихся множеств.
В амортизационном анализе каждой операции присваивается учетная стоимость (amortized cost), которая может отличаться от её фактической стоимости. Учетные стоимости выбираются таким образом, чтобы сумма учетных стоимостей для любой последовательности операций была не меньше суммы фактических стоимостей этих операций.
В методе группировки мы определяем верхнюю границу
Пример. Рассмотрим динамический массив, который увеличивает свой размер в два раза, когда он заполнен. Операция вставки элемента в массив имеет две возможные стоимости:
Анализ:
В худшем случае каждая вставка может потребовать
Однако, если мы рассмотрим последовательность
Общая стоимость
Амортизированная стоимость каждой вставки, полученная методом группировки, равна
Еще пример (multistack). Операции push
, pop
, multipop(k)
. Пусть сделано multipop
может вытолкнуть
MultiPop
не может быть больше Push
, тогда получаем:
Среднее:
В методе предоплаты мы "предоплачиваем" за "дорогие" операции, выполняя "дешевые" операции. "Предоплата" накапливается в виде "кредита", который затем используется для оплаты "дорогих" операций.
Основная идея.
Пример: мультистек с операцией multipop
Рассмотрим стек с операциями push
, pop
и multipop(k)
, которая удаляет
Учетные стоимости:
push
: 2
pop
: 0
multipop(k)
: 0
Анализ:
При каждом push
мы "предоплачиваем" 1 единицу "кредита" за будущий pop
этого элемента.
Операции pop
и multipop
оплачиваются за счет накопленного "кредита".
Поскольку каждый элемент может быть удален из стека только один раз, "кредита" всегда достаточно для оплаты всех операций.
Получаем
В методе потенциалов мы вводим потенциальную функцию Φ, которая отображает состояние структуры данных в неотрицательное число. Амортизированная стоимость операции определяется как сумма её фактической стоимости и изменения потенциальной функции.
Требования к потенциальной функции:
Φ(начальное состояние) = 0
Φ(любое состояние) ≥ 0
Анализ амортизированной стоимости операций:
Ограничения:
Потенциальная функция должна адекватно отражать "запас энергии" или "накопленную стоимость" в структуре данных.
Потенциальная функция должна быть достаточно простой для вычисления, чтобы не добавлять значительную дополнительную сложность к анализу алгоритма.
Потенциальная функция должна быть консервативной, то есть не должна искусственно занижать амортизированные затраты.
Замечание. Метод потенциалов является обобщением метода предоплаты.
Сумма разности потенциалов:
Пример: Бинарный счетчик
Рассмотрим бинарный счетчик, который хранит число в двоичном виде. Операция "increment" увеличивает число на 1.
Потенциальная функция: Φ(счетчик) = количество единиц в двоичном представлении числа.
Анализ:
Фактическая стоимость операции "increment" равна количеству битов, которые нужно перевернуть.
Изменение потенциальной функции равно разности между количеством единиц после и до операции "increment".
В худшем случае нужно перевернуть все биты, но при этом Φ уменьшается на
Амортизированная стоимость "increment" равна
Пример: multistack
Push:
Pop:
MultiPop:
Получаем
Система непересекающихся множеств (disjoint-set data structure) - это структура данных, которая поддерживает операции над коллекцией непересекающихся множеств.
Основные операции:
MakeSet(x): Создает новое множество, содержащее только элемент x.
Union(x, y): Объединяет множества, содержащие элементы x и y.
FindSet(x): Возвращает представителя множества, содержащего элемент x.
Оценка амортизированной стоимости операций:
С помощью амортизационного анализа можно показать, что амортизированная стоимость операций
Для достижения высокой эффективности операций Union и FindSet применяются две эвристики:
Объединение по рангу (Union by Rank): При объединении двух множеств дерево с меньшим рангом присоединяется к дереву с большим рангом. Ранг - это верхняя граница высоты дерева.
Сжатие пути (Path Compression): Во время операции FindSet все узлы на пути от x до корня переподключаются непосредственно к корню.
Для анализа амортизированной стоимости операций над disjoint-set data structure с использованием объединения по рангу и сжатия пути применим метод потенциалов.
Определим потенциальную функцию
где
MakeSet(x):
Фактическая стоимость:
Изменение потенциала:
Амортизированная стоимость:
Union(x, y):
Фактическая стоимость:
Изменение потенциала:
Если ранги корней равны, то ранг одного из корней увеличивается на 1, что приводит к увеличению потенциала на
Если ранги корней различны, то потенциал не изменяется.
Амортизированная стоимость:
FindSet(x):
Фактическая стоимость:
Изменение потенциала:
Сжатие пути уменьшает потенциал каждого узла на пути от
Суммарное уменьшение потенциала может быть оценено как
Амортизированная стоимость:
Итог:
Амортизированная стоимость операций
Замечания:
Функция α(n) растет настолько медленно, что на практике её можно считать константой.
Амортизированный анализ показывает, что в среднем операции над disjoint-set data structure выполняются очень быстро, несмотря на то, что некоторые отдельные операции могут быть "дорогими".
Графы — это мощные структуры данных, используемые для представления отношений между объектами. Они состоят из вершин (узлов) и ребер, соединяющих вершины. Графы находят широкое применение в различных областях, таких как социальные сети, транспортные системы, компьютерные сети и многие другие.
Граф — отображение
Если
Если
Матрица смежности - это двумерный массив, где строки и столбцы соответствуют вершинам графа. Элемент матрицы A[i][j]
равен 1, если существует ребро между вершинами i и j, и 0 в противном случае.
Преимущества:
Простота реализации.
Быстрая проверка наличия ребра между двумя вершинами.
Недостатки:
Требует
Неэффективна для разреженных графов (с небольшим количеством ребер).
1 | 2 | 3 | 4 | |
---|---|---|---|---|
1 | 0 | 1 | 1 | 0 |
2 | 1 | 0 | 1 | 1 |
3 | 1 | 1 | 0 | 1 |
4 | 0 | 1 | 1 | 0 |
Списки смежности - это набор списков, где каждый список соответствует вершине графа и содержит её смежные вершины (те, с которыми она соединена ребрами).
Преимущества:
Эффективна для разреженных графов.
Требует
Недостатки:
Менее эффективна для проверки наличия ребра между двумя вершинами.
Пример
1: [2, 3]
2: [1, 3, 4]
3: [1, 2, 4]
4: [2, 3]
Поиск в ширину (Breadth-First Search) - это алгоритм обхода графа, который сначала посещает все вершины, смежные с начальной вершиной, затем все вершины, смежные с этими вершинами, и так далее. BFS использует очередь для хранения вершин, которые нужно посетить.
Применение:
Нахождение кратчайшего пути в невзвешенном графе.
Проверка связности графа.
Конкретный пример:
Шаг 1: Посещаем вершину 1 и добавляем ее соседей (2 и 3) в очередь.
Шаг 2: Извлекаем из очереди вершину 2 и добавляем ее непосещенного соседа (4) в очередь.
Шаг 3: Извлекаем из очереди вершину 3. Ее соседи (2 и 4) уже посещены.
Шаг 4: Извлекаем из очереди вершину 4. У нее нет непосещенных соседей.
Итого: 1, 2, 3, 4
xxxxxxxxxx
91BFS(G, v)
2 opened.insert(v)
3 while (!opened.empty) begin
4 v = opened.pop
5 foreach u in adj(v) begin
6 if !(u in closed) and !(u in opened)
7 opened.insert(v)
8 end
9 end
opened
closed
Поиск в глубину (Depth-First Search) - это алгоритм обхода графа, который идет "вглубь" графа, посещая вершины, пока не достигнет тупика, а затем возвращается назад и исследует другие ветви. DFS использует стек (или рекурсию) для хранения вершин, которые нужно посетить.
Применение:
Нахождение сильно связных компонент.
Топологическая сортировка.
На примере:
Посещаем вершину 1. Вызываем рекурсивно DFS для соседа 2.
Посещаем вершину 2. Вызываем рекурсивно DFS для непосещенного соседа 4.
Посещаем вершину 4. Вызываем рекурсивно DFS для непосещенного соседа 3.
Посещаем вершину 3. У нее нет непосещенных соседей. Возвращаемся на шаг 3.
На шаге 3 все соседи вершины 4 посещены. Возвращаемся на шаг 2.
На шаге 2 все соседи вершины 2 посещены. Возвращаемся на шаг 1.
На шаге 1 все соседи вершины 1 посещены. Алгоритм завершает работу.
Итого: 1, 2, 4, 3
Примечание:
DFS не всегда дает единственно возможный порядок обхода. Он зависит от порядка выбора соседей для посещения
В данном примере мы предполагаем, что соседи выбираются в порядке их нумерации в графе.
xxxxxxxxxx
121DFS(G, v)
2 foreach v in G.V
3 v.d = 0 / inf / -inf
4 v.f = 0 / inf / -inf
5 DFS_Visit(v)
6
7DFS_Visit(v)
8 v.d = t++
9 foreach u in Adj(v)
10 if u.d < 0
11 DFS_Visit(u)
12 v.f = t++
Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных вершин во взвешенном графе с неотрицательными весами ребер. Алгоритм использует очередь с приоритетами для выбора вершины с наименьшим расстоянием от начальной вершины.
Инициализация:
Создаем таблицу расстояний distance
, где distance[v]
- текущее кратчайшее расстояние от вершины A до вершины v
. Изначально distance[A] = 0
, а для остальных вершин distance[v] = ∞
.
Создаем множество посещенных вершин visited
. Изначально оно пустое.
Добавляем вершину A в очередь с приоритетом queue
, упорядоченную по возрастанию расстояния.
Итерации: Пока очередь не пуста:
Извлекаем из очереди вершину u
с наименьшим расстоянием distance[u]
.
Добавляем вершину u
в множество visited
.
Для каждого соседа v
вершины u
:
Если v
не посещена и distance[u] + weight(u, v) < distance[v]
, то обновляем расстояние до v
: distance[v] = distance[u] + weight(u, v)
.
Добавляем вершину v
в очередь queue
.
Результат: После завершения алгоритма distance[F]
будет содержать длину кратчайшего пути из A в F.
Применение:
Навигационные системы.
Маршрутизация в сетях.
Пример.
Задача:
Найти кратчайший путь из вершины A в вершину F.
Шаг | Очередь queue (вершина, расстояние) | visited | distance (A, B, C, D, E, F) |
---|---|---|---|
1 | (A, 0) | {} | (0, ∞, ∞, ∞, ∞, ∞) |
2 | (B, 2), (C, 4) | {A} | (0, 2, 4, ∞, ∞, ∞) |
3 | (D, 3), (C, 4), (E, 5) | {A, B} | (0, 2, 4, 3, 5, ∞) |
4 | (C, 4), (E, 5), (F, 5) | {A, B, D} | (0, 2, 4, 3, 5, 5) |
5 | (E, 5), (F, 5) | {A, B, C, D} | (0, 2, 4, 3, 5, 5) |
6 | (F, 5) | {A, B, C, D, E} | (0, 2, 4, 3, 5, 5) |
7 | {} | {A, B, C, D, E, F} | (0, 2, 4, 3, 5, 5) |
Длина кратчайшего пути из A в F равна 5. Один из возможных путей: A -> B -> D -> F.
Алгоритм Крускала находит минимальное остовное дерево (MST) во взвешенном графе. MST - это подграф, содержащий все вершины графа и минимально возможную сумму весов ребер. Алгоритм сортирует ребра по весу и добавляет их в MST, если они не создают циклов
Сортировка ребер: Создаем список всех ребер графа и сортируем его по возрастанию веса:
xxxxxxxxxx
21(B, D, 1), (A, B, 2), (D, F, 2), (B, E, 3), (E, F, 3),
2(A, C, 4), (C, E, 6)
Инициализация:
Создаем пустое множество mst
, которое будет хранить ребра MST.
Создаем структуру данных для хранения компонент связности вершин (например, систему непересекающихся множеств). Изначально каждая вершина находится в своей компоненте.
Итерации: Проходим по отсортированному списку ребер:
Для каждого ребра (u, v)
:
Если вершины u
и v
находятся в разных компонентах связности:
Добавляем ребро (u, v)
в mst
.
Объединяем компоненты связности вершин u
и v
.
Результат: После обработки всех ребер множество mst
будет содержать ребра минимального остовного дерева.
Пример. Найти минимальное остовное дерево (MST) для этого графа.
Пошаговое выполнение:
Шаг | Ребро (u, v, вес) | mst | Компоненты связности |
---|---|---|---|
1 | (B, D, 1) | {(B, D, 1)} | {A}, {B, D}, {C}, {E}, {F} |
2 | (A, B, 2) | {(B, D, 1), (A, B, 2)} | {A, B, D}, {C}, {E}, {F} |
3 | (D, F, 2) | {(B, D, 1), (A, B, 2), (D, F, 2)} | {A, B, D, F}, {C}, {E} |
4 | (B, E, 3) | {(B, D, 1), (A, B, 2), (D, F, 2), (B, E, 3)} | {A, B, D, E, F}, {C} |
5 | (E, F, 3) | Пропускаем, т.к. E и F уже в одной компоненте | {A, B, D, E, F}, {C} |
6 | (A, C, 4) | {(B, D, 1), (A, B, 2), (D, F, 2), (B, E, 3), (A, C, 4)} | {A, B, C, D, E, F} |
7 | (C, E, 6) | Пропускаем, т.к. все вершины уже в одной компоненте | {A, B, C, D, E, F} |
xxxxxxxxxx
101MST_Kruskal(G, w)
2 A = []
3 for v in G.V
4 MakeSet(v)
5 G.E.sort() // по возрастанию
6 for u in G.E
7 if FindSet(u.from) != FindSet(u.to)
8 A.insert(u)
9 Union(u.from, u.to)
10 return A
aАлгоритм Прима также находит MST во взвешенном графе. Алгоритм начинает с произвольной вершины и добавляет к MST ребро с наименьшим весом, соединяющее вершину в MST с вершиной вне MST. Стоимость
Инициализация:
Выбираем произвольную вершину в качестве начальной (например, A).
Создаем множество mst
, которое будет хранить ребра MST. Изначально оно пустое.
Создаем таблицу key
, где key[v]
- вес ребра с минимальным весом, соединяющего вершину v
с деревом, построенным на данный момент. Изначально key[A] = 0
, а для остальных вершин key[v] = ∞
.
Создаем массив parent
, где parent[v]
- вершина, предшествующая вершине v
в MST. Изначально parent[A] = None
.
Создаем очередь с приоритетом queue
, содержащую все вершины графа. Приоритет вершины определяется значением key
.
Итерации: Пока очередь queue
не пуста:
Извлекаем из очереди вершину u
с минимальным ключом key[u]
.
Для каждого соседа v
вершины u
:
Если v
находится в очереди queue
и вес ребра (u, v)
меньше текущего ключа key[v]
:
Обновляем ключ: key[v] = weight(u, v)
.
Устанавливаем предка: parent[v] = u
.
Обновляем приоритет вершины v
в очереди queue
.
Пример.
Шаг | queue (вершина, ключ) | mst | key (A, B, C, D, E, F) | parent (A, B, C, D, E, F) |
---|---|---|---|---|
1 | (A, 0), (B, ∞), (C, ∞), (D, ∞), (E, ∞), (F, ∞) | {} | (0, ∞, ∞, ∞, ∞, ∞) | (None, None, None, None, None, None) |
2 | (B, 2), (C, 4), (D, ∞), (E, ∞), (F, ∞) | {} | (0, 2, 4, ∞, ∞, ∞) | (None, A, A, None, None, None) |
3 | (D, 3), (C, 4), (E, 5), (F, ∞) | {(A, B)} | (0, 2, 4, 3, 5, ∞) | (None, A, A, B, B, None) |
4 | (F, 5), (C, 4), (E, 5) | {(A, B), (B, D)} | (0, 2, 4, 3, 5, 5) | (None, A, A, B, B, D) |
5 | (C, 4), (E, 5) | {(A, B), (B, D), (D, F)} | (0, 2, 4, 3, 5, 5) | (None, A, A, B, B, D) |
6 | (E, 5) | {(A, B), (B, D), (D, F), (A, C)} | (0, 2, 4, 3, 5, 5) | (None, A, A, B, B, D) |
7 | {} | {(A, B), (B, D), (D, F), (A, C), (B, E)} | (0, 2, 4, 3, 5, 5) | (None, A, A, B, B, D) |
Топологическая сортировка ориентированного ациклического графа (DAG) — это линейное упорядочение всех его вершин таким образом, что для любого ребра (u, v) вершина u стоит раньше вершины v в этом порядке.
Note
Ориентированный ациклический граф (Directed Acyclic Graph, DAG) - это такой ориентированный граф, в котором отсутствуют циклы.
Дерево — это частный случай DAG, в котором каждая вершина (кроме корня) имеет ровно одного предка.
Применение:
Планирование задач.
Анализ зависимостей.
Алгоритм топологической сортировки (на основе поиска в глубину):
Инициализация:
Создаем список sorted
, который будет хранить отсортированные вершины.
Создаем словарь visited
, где visited[v]
- True, если вершина v
уже посещена, иначе False. Изначально все вершины не посещены.
Обход в глубину:
Для каждой вершины u
в графе:
Если вершина u
не посещена (visited[u] == False
):
Вызываем функцию dfs(u)
.
Функция dfs(u):
Помечаем вершину u
как посещенную: visited[u] = True
.
Для каждого соседа v
вершины u
:
Если вершина v
не посещена:
Рекурсивно вызываем dfs(v)
.
Добавляем вершину u
в начало списка sorted
.
Результат: После завершения алгоритма список sorted
будет содержать топологически отсортированные вершины.
Выполнение алгоритма:
Инициализация: sorted = []
, visited = {0: False, 1: False, 2: False, 3: False, 4: False, 5: False}
.
Обход в глубину:
dfs(5)
: Посещаем вершины 5, 2, 3, 1 (в таком порядке) и добавляем их в начало sorted
. sorted = [1, 3, 2, 5]
dfs(4)
: Посещаем вершины 4, 0, и добавляем их в начало sorted
. sorted = [0, 4, 1, 3, 2, 5]
Вызовы dfs(0)
, dfs(2)
, dfs(3)
, dfs(1)
не выполнятся, так как эти вершины уже посещены.
Результат: sorted = [0, 4, 1, 3, 2, 5]
- одна из возможных топологических сортировок данного графа.
Сильно связная компонента (SCC) - это максимальное подмножество вершин ориентированного графа, в котором существует путь между любой парой вершин. Алгоритм поиска SCC использует два прохода DFS для нахождения всех SCC в графе.
Применение:
Анализ социальных сетей.
Обнаружение циклов в графах.
Алгоритм:
STRONGLY-CONNECTED-COMPONENTS(G)
: Функция, запускающая алгоритм поиска SCC для графа G
.
Вызов DFS(G) для вычисления времен завершения u.f для каждой вершины u
:
Выполняем первый проход DFS на исходном графе G
.
Для каждой вершины u
записываем время ее завершения u.f
(время, когда рекурсивный вызов DFS для u
завершается).
Вычисление G^T
: Строим транспонированный граф G^T
, меняя направление всех ребер в G
.
Вызов DFS(G^T), но в основном цикле процедуры DFS вершины рассматриваются в порядке убывания значений u.f, вычисленных в строке 1
:
Выполняем второй проход DFS на транспонированном графе G^T
.
Ключевой момент: Вершины выбираются для запуска DFS в порядке убывания времен завершения, полученных в первом проходе.
Вывод вершин каждого дерева в лесу поиска в глубину, полученного в строке 3, в качестве отдельного сильно связного компонента
:
Каждое дерево в лесу DFS, построенном во втором проходе, представляет собой одну SCC.
Почему этот алгоритм работает?
Сортировка по времени завершения: Вершины с бо́льшим временем завершения в первом проходе DFS "глубже" расположены в графе.
Транспонированный граф: В транспонированном графе ребра "перевернуты", поэтому DFS из вершины u
в G^T
достигает только тех вершин, из которых можно добраться до u
в исходном графе G
.
Объединение: Запуская DFS из вершин в порядке убывания u.f
, мы гарантируем, что сначала будут найдены SCC, состоящие из "глубоких" вершин, а затем - из вершин, расположенных "выше" в графе.
Пример.
Рассмотрим ориентированный граф G
с вершинами A, B, C, D, E, F, G, H
и следующими ребрами:
Первый DFS и времена завершения. Выполняем DFS на графе G
(начальная вершина не важна) и записываем времена завершения для каждой вершины:
Время можно посчитать вот так:
xxxxxxxxxx
381def dfs_finish_times(graph):
2 visited = set()
3 finish_times = {}
4 time = 0
5
6 def dfs(node):
7 nonlocal time
8 visited.add(node)
9 time += 1
10
11 for neighbor in graph[node]:
12 if neighbor not in visited:
13 dfs(neighbor)
14
15 time += 1
16 finish_times[node] = time
17
18 for node in graph:
19 if node not in visited:
20 dfs(node)
21
22 return finish_times
23
24graph = {
25 'A': ['B'],
26 'B': ['C', 'D'],
27 'C': ['A'],
28 'D': ['E'],
29 'E': ['F'],
30 'F': ['D'],
31 'G': ['H'],
32 'H': ['G'],
33}
34
35finish_times = dfs_finish_times(graph)
36print(finish_times)
37
38# {'C': 4, 'F': 8, 'E': 9, 'D': 10, 'B': 11, 'A': 12, 'H': 15, 'G': 16}
A.f = 12
B.f = 11
C.f = 4
D.f = 10
E.f = 9
F.f = 8
G.f = 16
H.f = 15
Транспонированный граф. Строим транспонированный граф G^T
:
xxxxxxxxxx
91B -> A
2C -> B
3A -> C
4D -> B
5E -> D
6F -> E
7D -> F
8H -> G
9G -> H
Второй DFS на G^T в порядке убывания времен завершения:
Выполняем DFS на G^T
, выбирая вершины в порядке убывания u.f
:
G (G.f = 16)
: DFS из G
посещает H
. Это первая SCC: {G, H}
.
A (A.f = 12)
: DFS из A
посещает C, B
. Это вторая SCC: {A, C, B}
.
D (D.f = 10)
: DFS из D
посещает F, E
. Это третья SCC: {D, F, E}
.
Результат:
Алгоритм нашел три сильно связные компоненты в графе G
:
{G, H}
{A, C, B}
{D, F, E}
Хэш-таблицы — это эффективные структуры данных для реализации словарей, которые поддерживают операции вставки, удаления и поиска за время
Требования к хеш-функциям
Реализуются для любых данных
Размер выхода не зависит от размера входа
Необратимы
Хорошее перемешивание
Сложно скомпрометировать
Быстро считаются
Замечания. При создании хэш-функций стараются сделать так, чтобы количество коллизий было минимальным. Хэш-функции считаются за
Существует два основных метода разрешения коллизий (когда разные ключи отображаются на один индекс):
Открытая адресация:
При коллизии ищется другая свободная ячейка в таблице с помощью последовательности проб (probing sequence).
Линейное пробирование: Проверяются ячейки
Квадратичное пробирование: Проверяются ячейки
Двойное хеширование: Используется вторая хэш-функция
Маркеры.
Замечания.
Нормальная хэш-функция для каждого ключа должна перебирать все клетки таблицы.
Открытая адресация позволяет сохранить память.
Если из таблицы часть удалять, то она забивается маркерами DEL, что увеличивает время поиска, исправить проблему может создание новой таблицы (перехэширование).
Открытая адресация хорошо, когда мы работаем без удалений.
Таблицы на основе цепочек:
В каждой ячейке таблицы хранится список (цепочка) элементов, хэширующихся на этот индекс.
При коллизии новый элемент добавляется в список.
Время поиска элемента = время вставки этого элемента на момент, когда его еще не было в таблице.
Предположим, у нас есть хэш-таблица размером 10 и простая хэш-функция: сумма ASCII-кодов букв имени по модулю 10.
Вставим "Alice: 25" Хэш("Alice") = (65 + 108 + 105 + 99 + 101) % 10 = 478 % 10 = 8 Помещаем в ячейку 8: [8] -> Alice: 25
Вставим "Bob: 30" Хэш("Bob") = (66 + 111 + 98) % 10 = 275 % 10 = 5 Помещаем в ячейку 5: [5] -> Bob: 30
Вставим "Charlie: 35" Хэш("Charlie") = (67 + 104 + 97 + 114 + 108 + 105 + 101) % 10 = 696 % 10 = 6 Помещаем в ячейку 6: [6] -> Charlie: 35
Вставим "David: 28" Хэш("David") = (68 + 97 + 118 + 105 + 100) % 10 = 488 % 10 = 8 Коллизия! Ячейка 8 уже занята. Используем метод цепочек: [8] -> Alice: 25 -> David: 28
Теперь наша хэш-таблица выглядит так:
xxxxxxxxxx
101[0]
2[1]
3[2]
4[3]
5[4]
6[5] -> Bob: 30
7[6] -> Charlie: 35
8[7]
9[8] -> Alice: 25 -> David: 28
10[9]
Чтобы найти возраст Чарли, мы вычисляем хэш("Charlie") = 6, идем в ячейку 6 и получаем значение 35. Для поиска возраста Дэвида, мы вычисляем хэш("David") = 8, идем в ячейку 8, проходим по цепочке и находим нужную запись. Этот пример демонстрирует основные принципы работы хэш-таблицы, включая вставку, разрешение коллизий методом цепочек и поиск элементов.
Предположим, у нас та же хэш-таблица размером 10 и та же хэш-функция: сумма ASCII-кодов букв имени по модулю 10.
Вставим "Alice: 25" Хэш("Alice") = 8 Помещаем в ячейку 8: [8] Alice: 25
Вставим "Bob: 30" Хэш("Bob") = 5 Помещаем в ячейку 5: [5] Bob: 30
Вставим "Charlie: 35" Хэш("Charlie") = 6 Помещаем в ячейку 6: [6] Charlie: 35
Вставим "David: 28" Хэш("David") = 8 Ячейка 8 занята. Пробуем следующую: 9 Помещаем в ячейку 9: [9] David: 28
Вставим "Eve: 40" Хэш("Eve") = 8 Ячейки 8 и 9 заняты. Пробуем следующую: 0 Помещаем в ячейку 0: [0] Eve: 40
Теперь наша хэш-таблица выглядит так:
xxxxxxxxxx
101[0] Eve: 40
2[1]
3[2]
4[3]
5[4]
6[5] Bob: 30
7[6] Charlie: 35
8[7]
9[8] Alice: 25
10[9] David: 28
Поиск элемента. Чтобы найти возраст Чарли, мы вычисляем хэш("Charlie") = 6, идем в ячейку 6 и получаем значение 35.
Для поиска возраста Дэвида:
Вычисляем хэш("David") = 8
Проверяем ячейку 8 - там Alice
Проверяем следующую ячейку (9) - находим David: 28
Для поиска возраста Евы:
Вычисляем хэш("Eve") = 8
Проверяем ячейку 8 - там Alice
Проверяем ячейку 9 - там David
Проверяем ячейку 0 - находим Eve: 40
Удаление элемента. При удалении элемента в открытой адресации нельзя просто очистить ячейку, так как это может нарушить цепочку поиска для других элементов. Вместо этого обычно используют специальный маркер "удалено".
Например, если мы удалим "Alice": [8] DELETED
Этот пример демонстрирует, как работает открытая адресация с линейным пробированием для разрешения коллизий в хэш-таблице.
CHAIN | CHAIN (repeats) | OPEN ADR. | OPEN ADR. (repeats) | |
---|---|---|---|---|
Assert | … число проб | |||
Find | ||||
Remove |
Замечание. Так как размер таблицы заранее выбирается большой, то
Метод деления:
Метод умножения:
Универсальное хеширование: Используется семейство хэш-функций, выбираемых случайным образом.
Кластеризация: При открытой адресации коллизии могут приводить к образованию кластеров занятых ячеек, что увеличивает время поиска.
Удаление элементов: При открытой адресации удаление элементов может нарушить последовательности проб, что требует специальной обработки (использование маркеров).
Хэш-таблицы предоставляют эффективный способ реализации структуры данных "словарь" (dictionary), которая хранит пары "ключ-значение" и обеспечивает быстрый доступ к значению по ключу. Рассмотрим подробнее реализацию основных операций словаря с использованием хэш-таблицы:
1. Insert(key, value)
- Вставка пары (ключ, значение):
Вычисление хэш-значения: Вычисляем хэш ключа с помощью хэш-функции: index = hash(key) % table_size
.
Разрешение коллизий: Если ячейка index
уже занята другой парой с другим ключом:
Открытая адресация: Ищем следующую свободную ячейку в соответствии с выбранной стратегией пробирования (линейное, квадратичное, двойное хеширование).
Цепочки: Добавляем новую пару (ключ, значение) в список (цепочку), связанный с данной ячейкой.
Вставка: Помещаем новую пару (ключ, значение) в найденную свободную ячейку или в список.
2. Delete(key)
- Удаление пары с заданным ключом:
Поиск ячейки: Вычисляем хэш ключа и находим соответствующую ячейку, как при операции Search
.
Удаление:
Открытая адресация: Помечаем ячейку как удаленную (например, специальным маркером), не удаляя данные физически, чтобы не нарушать логику пробирования.
Цепочки: Удаляем пару (ключ, значение) из списка, связанного с данной ячейкой.
3. Search(key)
- Поиск значения по ключу:
Вычисление хэш-значения: Вычисляем хэш ключа.
Поиск в таблице:
Открытая адресация: Проверяем ячейку, соответствующую хэшу ключа. Если ключ не совпадает, применяем стратегию пробирования, пока не найдем нужный ключ или пустую ячейку (ключ не найден).
Цепочки: Проходим по списку, связанному с вычисленным хэшем, и сравниваем ключи элементов списка с искомым.
Пример реализации:
xxxxxxxxxx
701
2
3
4
5using namespace std;
6
7template <typename Key, typename Value>
8class HashTable {
9private:
10 vector<list<pair<Key, Value>>> table;
11 size_t capacity;
12
13 size_t _hash(const Key& key) const {
14 return hash<Key>{}(key) % capacity;
15 }
16
17public:
18 HashTable(size_t capacity) : capacity(capacity), table(capacity) {}
19
20 void insert(const Key& key, const Value& value) {
21 size_t index = _hash(key);
22 table[index].emplace_back(key, value);
23 }
24
25 Value* search(const Key& key) {
26 size_t index = _hash(key);
27 for (auto& pair : table[index]) {
28 if (pair.first == key) {
29 return &pair.second;
30 }
31 }
32 return nullptr; // Key not found
33 }
34
35 void erase(const Key& key) {
36 size_t index = _hash(key);
37 auto& list = table[index];
38 for (auto it = list.begin(); it != list.end(); ++it) {
39 if (it->first == key) {
40 list.erase(it);
41 return;
42 }
43 }
44 // Key not found, throw an exception or handle accordingly
45 }
46};
47
48int main() {
49 HashTable<string, int> table(10);
50 table.insert("apple", 1);
51 table.insert("banana", 2);
52
53 int* value = table.search("banana");
54 if (value != nullptr) {
55 cout << "Value for 'banana': " << *value << endl;
56 } else {
57 cout << "Key 'banana' not found" << endl;
58 }
59
60 table.erase("apple");
61
62 value = table.search("apple");
63 if (value != nullptr) {
64 cout << "Value for 'apple': " << *value << endl;
65 } else {
66 cout << "Key 'apple' not found" << endl;
67 }
68
69 return 0;
70}
Важно:
Выбор хэш-функции и стратегии разрешения коллизий влияет на производительность операций словаря.
Обработка ошибок. Например, обработка ситуации, когда ключ не найден при удалении или поиске.
Динамическое изменение размера. При большом количестве элементов может потребоваться увеличить размер таблицы и перехешировать данные для поддержания производительности.
Хеширование с перескоком (Hopscotch hashing):
Рассматривает «окружение» ячейки, которое формирует «ведерко» (bucket). Элемент размещается не дальше окружения ячейки, совпадающей с хэшем.
Общая идея:
Если ячейка
Начиная с
Если
Иначе найти
Если ничего не удалось, то перестроить таблицу.
xxxxxxxxxx
31↓ H-bucket ↓
2... | |z| | |x| | ...
3h(x)-^.->->.^
Если все занято: ищем элемент, который можно выгнать (т.к. bucket’ы накладываются). Двигаем, пока не найдем пустую ячейку для всех «выгнанных» элементов.
Если все занято 2: ищем первую свободную ячейку. Далее, возвращаясь назад, ищем элемент, который можно переместить в эту ячейку. Перемещаем, пока не найдем место для вставленного элемента.
Если все занято — отказ.
Достоинства: быстрый поиск и удаление, т.к. не рассматриваем хэширование дальше bucket’а.
Хеширование Робин Гуда (Robin Hood hashing):
Обычное хэширование с контролем номера пробы. Если встречаем при вставке элемент с меньшим числом проб, то вытесняем его и ищем ему другое место.
Достоинства: быстрый поиск и удаление.
Двухвыборное хеширование:
Используется две хэш-функции, и элемент вставляется в ту ячейку, где меньше коллизий.
Таблица на цепочках.
Балансирует длины списков.
Уменьшает вероятность кластеризации.
Кукушкино хеширование (Cuckoo hashing):
Обычно на
Используется две или более хэш-функции и две или более таблицы.
Элемент может быть помещен в одну из двух ячеек, определяемых хэш-функциями.
При коллизии элемент "выталкивается" из своей ячейки и перемещается в другую таблицу, что может вызвать цепочку перемещений.
Гарантирует время поиска
Проблема: может зациклиться, может быть долга вставка.
В целом, можно две хэш-функции использовать в одной таблице.
Достоинство: быстрый поиск, близко к массиву, быстрое удаление.
Bloom Filter позволяет проверить принадлежность элемента множеству. Может ложно подтвердить наличие элемента при его отсутствии. Если подтверждает отсутствие, то это всегда истина.
Общая идея:
xxxxxxxxxx
51|h1 |h2 |h3 # Вставка / вставленная строка
2V V V
3... |1| |1| |0| |1| | ...
4^ ^ ^
5|h1 |h2 |h3 # Поиск / значит такой строки нет
Замечание. Удалять из Фильтра Блума нельзя. Но работает с объединением фильров. Используется в ситуациях, когда требуется высокая эффективность по времени и памяти.
Куча — это структура данных, представляющая собой полное бинарное дерево, для которого выполняется свойство кучи. Существуют два основных типа куч:
max-куча: ключ каждого узла больше или равен ключам его потомков.
min-куча: ключ каждого узла меньше или равен ключам его потомков.
Двоичная куча (binary heap) — это наиболее распространенная реализация кучи, которая использует массив для хранения элементов дерева.
Свойства:
Полное бинарное дерево: Все уровни дерева заполнены, кроме, возможно, последнего, который заполняется слева направо.
Свойство кучи: Для каждого узла выполняется свойство max-кучи или min-кучи.
Куча не сохраняет валидность итераторов при операциях с ней.
Представление в массиве:
Корень дерева находится в ячейке с индексом 1.
Для узла с индексом
Левый потомок:
Правый потомок:
Родитель:
Высота кучи:
Число слоев:
Количество элементов:
Heapify(A, i)
: Восстанавливает свойство кучи для поддерева с корнем в узле
BuildHeap(A)
: Строит кучу из неупорядоченного массива
ExtractMax(A)
(для max-кучи) / ExtractMin(A)
(для min-кучи): Извлекает и возвращает максимальный (минимальный) элемент из кучи.
Insert(A, key)
: Вставляет новый ключ
IncreaseKey(A, i, key)
(для max-кучи) / DecreaseKey(A, i, key)
(для min-кучи): Увеличивает (уменьшает) значение ключа в узле
Примеры реализации на псевдокоде:
1. Heapify(A, i)
:
x1Heapify(A, i)
2 left = 2 * i
3 right = 2 * i + 1
4 largest = i
5
6 // Находим индекс наибольшего элемента среди узла i, его левого и правого потомков
7 if left <= heap_size(A) and A[left] > A[largest] then
8 largest = left
9 end if
10
11 if right <= heap_size(A) and A[right] > A[largest] then
12 largest = right
13 end if
14
15 // Если наибольший элемент не в узле i, меняем местами и рекурсивно вызываем Heapify
16 if largest != i then
17 swap(A[i], A[largest])
18 Heapify(A, largest)
19 end if
2. BuildHeap(A)
:
xxxxxxxxxx
51BuildHeap(A)
2 // Начинаем с последнего нелистового узла и идем к корню
3 for i = floor(heap_size(A) / 2) downto 1 do
4 Heapify(A, i)
5 end for
3. ExtractMax(A)
:
xxxxxxxxxx
101ExtractMax(A)
2 if heap_size(A) < 1 then
3 error "Куча пуста"
4 end if
5
6 max = A[1] // Максимальный элемент всегда в корне
7 A[1] = A[heap_size(A)] // Перемещаем последний элемент в корень
8 heap_size(A) = heap_size(A) - 1 // Уменьшаем размер кучи
9 Heapify(A, 1) // Восстанавливаем свойство кучи
10 return max
4. Insert(A, key)
:
Элемент добавляется в конец массива, сравнивается с родителем. Если родитель больше, то они меняются местами и сравнение продолжается, пока родитель не окажется меньше или элемент не станет корнем.
xxxxxxxxxx
101Insert(A, key)
2 heap_size(A) = heap_size(A) + 1 // Увеличиваем размер кучи
3 A[heap_size(A)] = key // Вставляем новый ключ в конец массива
4 i = heap_size(A)
5
6 // Восстанавливаем свойство кучи, поднимая новый ключ вверх
7 while i > 1 and A[parent(i)] < A[i] do
8 swap(A[i], A[parent(i)])
9 i = parent(i)
10 end while
5. IncreaseKey(A, i, key)
:
xxxxxxxxxx
121IncreaseKey(A, i, key)
2 if key < A[i] then
3 error "Новый ключ меньше текущего"
4 end if
5
6 A[i] = key // Увеличиваем значение ключа
7
8 // Восстанавливаем свойство кучи, поднимая измененный ключ вверх
9 while i > 1 and A[parent(i)] < A[i] do
10 swap(A[i], A[parent(i)])
11 i = parent(i)
12 end while
6. Pop(A)
:
xxxxxxxxxx
41Pop(A)
2 A[0] = A[N - 1]
3 N--
4 Heapify(A, 0)
Куча позволяет удалять только корень.
Вспомогательные функции:
heap_size(A)
: возвращает текущий размер кучи (количество элементов).
parent(i)
: возвращает индекс родительского узла для узла с индексом
swap(x, y)
: меняет местами значения переменных
Важно:
В этом псевдокоде предполагается, что индексация массива начинается с 1.
Реализация heap_size
может быть разной в зависимости от выбранной структуры данных (массив фиксированного размера или динамический массив).
Алгоритм сортировки с помощью двоичной кучи (Heap Sort) состоит из двух этапов:
Построение кучи: BuildHeap(A)
преобразует исходный массив в max-кучу.
Сортировка:
Повторяем
Извлекаем максимальный элемент из кучи: max = ExtractMax(A)
.
Помещаем
Уменьшаем размер кучи на 1.
Еще как вариант:
xxxxxxxxxx
91HeapSort(A)
2 N = len(A)
3 BuildHeap(A)
4 for i = N - 1 to 1 do begin
5 swap(A[0], A[N - 1])
6 N--
7 Heapify(A, 0)
8 end
9 return A
Heapify(A, i)
:
BuildHeap(A)
:
ExtractMax(A)
/ ExtractMin(A)
:
Insert(A, key)
:
IncreaseKey(A, i, key)
/ DecreaseKey(A, i, key)
:
Heap Sort
:
Pop(A)
:
Переборные алгоритмы (brute-force algorithms) — это алгоритмы, которые основаны на полном переборе всех возможных решений задачи. Они гарантированно находят оптимальное решение, но могут быть очень неэффективными для задач с большим пространством решений.
Полный перебор (exhaustive search) — это простейшая стратегия перебора, которая заключается в проверке всех возможных решений без каких-либо оптимизаций.
Пример: Задача коммивояжера
В задаче коммивояжера (Traveling Salesman Problem, TSP) нужно найти кратчайший маршрут, проходящий через все города ровно один раз и возвращающийся в исходный город.
Полный перебор: Генерируем все возможные перестановки городов и вычисляем длину маршрута для каждой перестановки. Выбираем перестановку с минимальной длиной.
Сложность:
Метод ветвей и границ (Branch and Bound) — это более эффективная стратегия перебора, которая использует оценки для отсечения заведомо неоптимальных решений.
Идея:
Разбиение: Разбиваем пространство решений на подмножества (ветви).
Оценка: Для каждой ветви вычисляем нижнюю границу (lower bound) для оптимального решения в этой ветви.
Отсечение: Если нижняя граница для ветви больше, чем текущее наилучшее решение, то эту ветвь можно отсечь, так как она не может содержать оптимального решения.
Рекурсия: Рекурсивно применяем метод ветвей и границ к оставшимся ветвям.
Разбиение: На каждом шаге выбираем город, который еще не посещен, и создаем ветви для каждого возможного следующего города.
Оценка: Нижняя граница для ветви может быть вычислена как сумма длин уже пройденных ребер и минимальных длин ребер, соединяющих оставшиеся города.
Отсечение: Если нижняя граница для ветви больше, чем текущая минимальная длина маршрута, то эту ветвь можно отсечь.
Пример реализации на псевдокоде (упрощенный):
xxxxxxxxxx
191BranchAndBound(cities, current_city, visited, current_length, best_length)
2 if visited == all_cities then
3 // Посетили все города, проверяем длину маршрута
4 if current_length < best_length then
5 best_length = current_length
6 end if
7 return
8 end if
9
10 // Перебираем непосещенные города
11 for next_city in cities where next_city not in visited do
12 // Вычисляем нижнюю границу для ветви
13 lower_bound = current_length + distance(current_city, next_city) + min_remaining_distances(cities, visited)
14
15 // Отсекаем ветвь, если ее нижняя граница больше текущего лучшего решения
16 if lower_bound < best_length then
17 BranchAndBound(cities, next_city, visited + next_city, current_length + distance(current_city, next_city), best_length)
18 end if
19 end for
Динамическое программирование (dynamic programming) — это мощный метод решения задач, который основан на разбиении задачи на подзадачи и использовании решений подзадач для решения исходной задачи. Он применим к задачам, которые обладают свойством оптимальной подструктуры и свойством перекрывающихся подзадач.
Свойство оптимальной подструктуры: Оптимальное решение задачи может быть построено из оптимальных решений её подзадач.
Свойство перекрывающихся подзадач: В процессе решения задачи одни и те же подзадачи возникают многократно.
Разбиение на подзадачи: Разбиваем задачу на подзадачи меньшего размера.
Рекуррентное соотношение: Записываем рекуррентное соотношение, выражающее решение задачи через решения её подзадач.
Запоминание решений: Сохраняем решения подзадач в таблице (или другой структуре данных), чтобы избежать повторных вычислений.
Построение решения: Используем таблицу с сохраненными решениями для построения решения исходной задачи.
Рекурсивный подход: Реализуем рекурсивную функцию, которая вычисляет решение задачи.
Мемоизация: Перед вычислением решения подзадачи проверяем, не было ли оно уже вычислено ранее. Если решение найдено в таблице, используем его; иначе, вычисляем решение и сохраняем его в таблице.
Мемоизация — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ.
Итеративный подход: Заполняем таблицу с решениями подзадач, начиная с самых маленьких подзадач и двигаясь к исходной задаче.
Использование рекуррентного соотношения: Для вычисления решения каждой подзадачи используем рекуррентное соотношение и уже вычисленные решения меньших подзадач.
Задача: Найти оптимальный порядок перемножения цепочки матриц, минимизирующий количество скалярных умножений.
Динамическое программирование:
Подзадачи: Перемножение подцепочек матриц.
Рекуррентное соотношение: m[i, j] = min(m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j])
, где m[i, j]
- минимальное количество умножений для перемножения матриц от i
до j
, а p
- массив размерностей матриц.
Запоминание: Таблица m
.
Построение решения: Восстановление оптимального порядка умножения из таблицы m
.
xxxxxxxxxx
281function matrix_chain_order(p):
2 // p - массив размерностей матриц, где p[i-1] x p[i] - размерность i-й матрицы
3 n = length(p) - 1 // Количество матриц
4
5 // Инициализируем таблицу m нулями
6 m = create_matrix(n, n, 0)
7
8 // Заполняем таблицу m по диагоналям, начиная с главной диагонали
9 for l = 2 to n: // l - длина цепочки матриц
10 for i = 1 to n - l + 1:
11 j = i + l - 1
12 m[i][j] = infinity
13 for k = i to j - 1:
14 q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]
15 if q < m[i][j]:
16 m[i][j] = q
17 s[i][j] = k // Сохраняем индекс k для восстановления порядка умножения
18
19 // Восстанавливаем порядок умножения из таблицы s
20 return get_optimal_parenthesization(s, 1, n)
21
22function get_optimal_parenthesization(s, i, j):
23 // Рекурсивно строим строку с оптимальным порядком умножения
24 if i == j:
25 return "A" + str(i)
26 else:
27 return "(" + get_optimal_parenthesization(s, i, s[i][j]) +
28 get_optimal_parenthesization(s, s[i][j]+1, j) + ")"
Задача: Найти наибольшую общую подпоследовательность двух последовательностей.
Динамическое программирование:
Подзадачи: LCS для префиксов последовательностей.
Рекуррентное соотношение: c[i, j] = c[i-1, j-1] + 1
, если x[i] == y[j]
, иначе c[i, j] = max(c[i-1, j], c[i, j-1])
, где c[i, j]
- длина LCS для префиксов x[1..i]
и y[1..j]
.
Запоминание: Таблица c
.
Построение решения: Восстановление LCS из таблицы c
.
xxxxxxxxxx
301function lcs_length(x, y):
2 // x, y - входные последовательности
3 m = length(x)
4 n = length(y)
5
6 // Инициализируем таблицу c нулями
7 c = create_matrix(m + 1, n + 1, 0)
8
9 // Заполняем таблицу c
10 for i = 1 to m:
11 for j = 1 to n:
12 if x[i] == y[j]:
13 c[i][j] = c[i-1][j-1] + 1
14 else:
15 c[i][j] = max(c[i-1][j], c[i][j-1])
16
17 // Восстанавливаем LCS из таблицы c
18 return backtrack_lcs(c, x, y, m, n)
19
20function backtrack_lcs(c, x, y, i, j):
21 // Рекурсивно восстанавливаем LCS
22 if i == 0 or j == 0:
23 return ""
24 elseif x[i] == y[j]:
25 return backtrack_lcs(c, x, y, i-1, j-1) + x[i]
26 else:
27 if c[i-1][j] > c[i][j-1]:
28 return backtrack_lcs(c, x, y, i-1, j)
29 else:
30 return backtrack_lcs(c, x, y, i, j-1)
Задача: Выбрать предметы из набора, чтобы максимизировать суммарную ценность, не превышая ограничение по весу.
Динамическое программирование:
Подзадачи: Максимальная ценность для подмножеств предметов и ограничений по весу.
Рекуррентное соотношение: dp[i, w] = max(dp[i-1, w], dp[i-1, w-w[i]] + v[i])
, если w[i] <= w
, иначе dp[i, w] = dp[i-1, w]
, где dp[i, w]
- максимальная ценность для предметов от 1 до i
и ограничения по весу w
.
Запоминание: Таблица dp
.
Построение решения: Восстановление набора предметов из таблицы dp
.
xxxxxxxxxx
281function knapsack(W, w, v):
2 // W - максимальный вес рюкзака
3 // w - массив весов предметов
4 // v - массив ценностей предметов
5 n = length(w)
6
7 // Инициализируем таблицу dp нулями
8 dp = create_matrix(n + 1, W + 1, 0)
9
10 // Заполняем таблицу dp
11 for i = 1 to n:
12 for w_cur = 1 to W:
13 if w[i] <= w_cur:
14 dp[i][w_cur] = max(dp[i-1][w_cur], dp[i-1][w_cur-w[i]] + v[i])
15 else:
16 dp[i][w_cur] = dp[i-1][w_cur]
17
18 // Восстанавливаем набор предметов из таблицы dp
19 return backtrack_knapsack(dp, w, n, W)
20
21function backtrack_knapsack(dp, w, i, w_cur):
22 // Рекурсивно восстанавливаем набор предметов
23 if i == 0 or w_cur == 0:
24 return []
25 elseif dp[i][w_cur] == dp[i-1][w_cur]:
26 return backtrack_knapsack(dp, w, i-1, w_cur)
27 else:
28 return backtrack_knapsack(dp, w, i-1, w_cur-w[i]) + [i]
Жадные алгоритмы (greedy algorithms) - это алгоритмы, которые на каждом шаге делают локально оптимальный выбор в надежде, что это приведет к глобально оптимальному решению. Они часто просты в реализации и эффективны, но не всегда гарантируют нахождение оптимального решения.
Жадный выбор: На каждом шаге можно сделать локально оптимальный выбор, не учитывая будущие последствия.
Оптимальная подструктура: Оптимальное решение задачи содержит оптимальные решения её подзадач.
Важно: Не все задачи, обладающие свойством оптимальной подструктуры, могут быть решены жадными алгоритмами.
В непрерывном варианте задачи о рюкзаке (Fractional Knapsack Problem) можно брать части предметов.
Задача: Имеется рюкзак с максимальной грузоподъемностью W
и набор предметов, каждый из которых имеет вес w[i]
и ценность v[i]
. Нужно выбрать предметы (или их части) так, чтобы максимизировать суммарную ценность, не превышая ограничение по весу.
Жадный алгоритм:
Вычисление удельной ценности: Для каждого предмета вычисляем удельную ценность v[i] / w[i]
.
Сортировка: Сортируем предметы по убыванию удельной ценности.
Заполнение рюкзака:
Начинаем с предмета с наибольшей удельной ценностью.
Берем весь предмет, если его вес не превышает оставшуюся грузоподъемность рюкзака.
Иначе, берем часть предмета, заполняющую оставшуюся грузоподъемность.
Псевдокод:
xxxxxxxxxx
281function fractional_knapsack(W, w, v):
2 // W - максимальный вес рюкзака
3 // w - массив весов предметов
4 // v - массив ценностей предметов
5 n = length(w)
6
7 // Вычисляем удельные ценности
8 specific_values = [v[i] / w[i] for i in range(n)]
9
10 // Сортируем предметы по убыванию удельной ценности
11 sorted_items = sort_by_descending(specific_values)
12
13 total_value = 0
14 remaining_weight = W
15
16 for i in sorted_items:
17 if w[i] <= remaining_weight:
18 // Берем весь предмет
19 total_value += v[i]
20 remaining_weight -= w[i]
21 else:
22 // Берем часть предмета
23 fraction = remaining_weight / w[i]
24 total_value += fraction * v[i]
25 remaining_weight = 0
26 break // Рюкзак заполнен
27
28 return total_value
Гарантия оптимальности:
Жадный алгоритм для непрерывного варианта задачи о рюкзаке гарантированно находит оптимальное решение.
Важно: Жадный алгоритм не работает для дискретного варианта задачи о рюкзаке, где нельзя брать части предметов.
Алгоритмы поиска подстрок (string matching algorithms) — это алгоритмы, предназначенные для поиска вхождений одной строки (образца, pattern) в другую строку (текст, text). Они широко используются в текстовых редакторах, поисковых системах, биоинформатике и других областях.
Задача: найти все вхождения подстроки в строку.
Если
Задача: для заданного образца найти все допустимые сдвиги.
"Наивный" алгоритм (naive algorithm) — это простейший алгоритм поиска подстрок, который заключается в последовательном сравнении образца с каждым возможным подстрокой текста.
Идея:
Для каждого индекса i
в тексте:
Сравниваем образец с подстрокой текста, начинающейся с i
.
Если все символы совпадают, то найдено вхождение образца.
Сложность: m
- длина образца, n
- длина текста.
Псевдокод:
xxxxxxxxxx
91Naive_Matcher(T, P):
2 for s = 0 to T.length - P.length
3 valid = true
4 for i = 1 to P.length
5 if T[s + i] != P[i]
6 valid = false
7 break
8 if vaild
9 print("Допустимый сдвиг:", s)
Алгоритм Рабина-Карпа (Rabin-Karp algorithm) использует хеширование для ускорения поиска подстрок.
Идея:
Вычисляем хэш образца.
Для каждого индекса i
в тексте:
Вычисляем хэш подстроки текста длины m
, начинающейся с i
.
Если хэши совпадают, сравниваем образец и подстроку текста посимвольно, чтобы убедиться, что это не ложное срабатывание (hash collision).
Пример. P.length
в число, сам паттерн тоже в число. Сравнить. Сдвинуться на один вправо. Подразумеваем, что код символа = его значение.
xxxxxxxxxx
51t_{i-1}
2v...v
3|1|2|7|1|3|2| ...
4|^...^ - t_i
5shift>|
Получается вычисление
Тогда получаем алгоритм:
xxxxxxxxxx
111RK(T, P):
2 q = 1; t = 0; p = 0
3 for i = 1 to m:
4 q = q * d
5 t = (d * t + T[i]) % q
6 p = (d * p + P[i]) % q
7 for s = 0 to n - m:
8 if t == p:
9 print("Сдвиг", s)
10 if s < n - m:
11 t = (((t - T[s + 1] * q) % q) * d + T[s + m + 1]) % q
q
: Переменная, хранящая текущую степень d
(начинает с 1 и увеличивается в степени d
на каждой итерации первого цикла). Используется для "сдвига" хэша влево.
t
: Хэш текущей подстроки текста T
длины m
.
p
: Хэш образца P
.
d
: Основание системы счисления, используемое для хэширования.
Возможно возникновение коллизии, в таком случае, если совпадает образец по коду, то сделать посимвольную проверку.
Оценка стоимости
Алгоритм Кнута-Морриса-Пратта (Knuth-Morris-Pratt algorithm) использует префикс-функцию для оптимизации поиска подстрок.
Идея:
Вычисляем префикс-функцию для образца. Префикс-функция pi[i]
для индекса i
в образце - это длина наибольшего собственного суффикса подстроки pattern[0..i]
, который также является префиксом образца.
Используем префикс-функцию для сдвига образца при несовпадении символов, избегая повторных сравнений уже проверенных символов.
Сдвигаем паттерн так, чтобы рассматриваемая часть сразу не конфликтовала с паттерном. Пример нахождения префикса в префикс-функции:
Обязательно
xxxxxxxxxx
251Compute_Prefix_Function(P):
2 m = P.length
3 pi[1...m]
4 pi[1] = 0
5 k = 0
6 for q = 2 to m do:
7 while (k > 0) and (P[k + 1] != P[q]):
8 k = pi[k]
9 if P[k + 1] == P[q]:
10 k++
11 pi[q] = k
12 return pi
13
14KMP_Matcher(T, P):
15 n = T.length; m = P.length
16 pi = Compute_Prefix_Function(P)
17 q = 0
18 for i = 1 to n do:
19 while (q > 0) and (P[q + 1] != T[i]):
20 q = pi[q]
21 if (P[q + 1] == T[i]):
22 q++
23 if q == m:
24 print("Образец со сдвигом", i - m)
25 q = pi[q]
Сложность:
Алгоритм Бойера-Мура (Boyer-Moore algorithm) использует два эвристических правила для ускорения поиска, при этом сравниваем с конца образца и начала фрагмента текста:
Правило плохого символа (bad character rule): При несовпадении символов сдвигаем образец так, чтобы последний символ образца совпал с соответствующим символом в тексте. Если выдается отрицательный сдвиг, то игнорируем рекомендацию этой эвристики.
Правило хорошего суффикса (good suffix rule): При совпадении суффикса образца с подстрокой текста сдвигаем образец так, чтобы этот суффикс совпал с предыдущим вхождением этого суффикса в образце. Всегда дает положительный сдвиг.
Общая идея алгоритма:
Выбираем наибольший сдвиг из двух эвристик.
Просматриваем текст с начала, паттерн с конца.
Примечание. Алгоритм хорош для больших последовательностей.
Сложность:
xxxxxxxxxx
741Boyer_Moore_Matcher(T, P):
2 n = длина(T) // Длина текста
3 m = длина(P) // Длина паттерна
4 occurrences = [] // Список индексов вхождений
5
6 // Предварительное вычисление таблиц для эвристик
7 bad_char = Bad_Character_Heuristic(P)
8 good_suffix = Good_Suffix_Heuristic(P)
9
10 s = 1 // Начальный сдвиг паттерна
11
12 while s <= n - m:
13 j = m // Индекс в паттерне, начинаем с конца
14
15 // Сравниваем символы паттерна и текста справа налево
16 while j > 0 and P[j] == T[s + j]:
17 j--
18
19 if j == 0: // Паттерн найден
20 добавить(occurrences, s) // Добавляем индекс вхождения в список
21 s = s + good_suffix[0] // Сдвигаем на величину хорошего суффикса
22 else:
23 // Считаем сдвиги по эвристикам
24 bad_char_shift = bad_char.получить(T[s + j - 1], m) // Сдвиг по плохому символу
25 good_suffix_shift = good_suffix[j + 1] // Сдвиг по хорошему суффиксу
26
27 // Выбираем максимальный сдвиг
28 s = s + max(bad_char_shift, good_suffix_shift)
29
30 return occurrences
31
32
33Bad_Character_Heuristic(P):
34 m = длина(P)
35 bad_char = словарь() // Создаем пустой словарь
36
37 // Заполняем словарь значениями по умолчанию
38 для i от 1 до m:
39 bad_char[P[i]] = m
40
41 // Заполняем словарь фактическими сдвигами
42 для i от 1 до m - 1:
43 bad_char[P[i]] = m - i
44
45 return bad_char
46
47
48Good_Suffix_Heuristic(P):
49 m = длина(P)
50 good_suffix = массив(m + 1) // Создаем массив размером m + 1
51 f = массив(m + 1) // Вспомогательный массив
52
53 // Инициализация массивов
54 f[m] = m + 1
55 i = m
56 j = m + 1
57
58 while i > 0:
59 while j <= m and P[i] != P[j]:
60 if good_suffix[j] == m:
61 good_suffix[j] = j - i
62 j = f[j]
63 i = i - 1
64 j = j - 1
65 f[i] = j
66
67 j = f[0]
68 for i от 1 до m + 1:
69 if good_suffix[i] == m:
70 good_suffix[i] = j
71 if i == j:
72 j = f[j]
73
74 return good_suffix
Для поиска подстрок можно построить конечный автомат, который принимает текст на вход и переходит в состояние "найдено", если текущая подстрока текста совпадает с образцом.
Конечный автомат
Для каждого паттерна строится свой конечный автомат.
Идея:
Строим конечный автомат для образца.
Пропускаем текст через автомат, начиная с начального состояния.
Если автомат переходит в допускающее состояние, то найдено вхождение образца.
Суффикс-функция
xxxxxxxxxx
31| | | | |#|#|#| x
2|#|#|#| | | | | | p
3^-k
Функция переходов:
xxxxxxxxxx
41[ ]
2| | |c|a|b|a|a| T
3|a|b|a|b| | | | | | p
4[ P_3 ]
Инвариант функции показывает конечное состояние автомата после прочтения
Алгоритм.
xxxxxxxxxx
191Finite_Automation_Matcher(T, P):
2 delta = Compute_Transition_Function(P, sigma)
3 n = T.length; m = P.length
4 q = 0
5 for i = 1 to n:
6 q = delta(q, T[i])
7 if q == m:
8 print("Образец со сдвигом", i-m)
9
10Compute_Transition_Matcher(P, sigma):
11 m = P.Length
12 for q = 0 to m:
13 for a in sigma:
14 k = min(m + 1, q + 2)
15 repeat
16 k--
17 until Pk in Pqa
18 delta(q, a) = k
19 return q
Оценка
Пример автомата. Конечный автомат для поиска подстроки "aba"
Состояние \ Вход | a | b | Другие |
---|---|---|---|
0 | 1 | 0 | 0 |
1 | 1 | 2 | 0 |
2 | 3 | 0 | 0 |
3 | 1 | 0 | 0 |
Пример работы автомата:
Входная строка: "aabababaa"
Шаг | Вход | Текущее состояние | Следующее состояние | Подстрока найдена? |
---|---|---|---|---|
1 | a | 0 | 1 | Нет |
2 | a | 1 | 1 | Нет |
3 | b | 1 | 2 | Нет |
4 | a | 2 | 3 | Да |
5 | b | 3 | 0 | Нет |
6 | a | 0 | 1 | Нет |
7 | b | 1 | 2 | Нет |
8 | a | 2 | 3 | Да |
Вывод: Подстрока "aba" найдена дважды, начиная с позиций 3 и 8.
Биномиальное дерево - это рекурсивно определяемая структура данных, используемая для реализации биномиальных куч.
Определение:
Биномиальное дерево порядка
Биномиальное дерево порядка
Свойства:
Биномиальное дерево порядка
Высота биномиального дерева порядка
В биномиальном дереве порядка
Биномиальная куча - это структура данных, представляющая собой набор биномиальных деревьев, которые удовлетворяют свойству кучи (min-куча или max-куча) и свойству биномиальной кучи.
Свойства:
Свойство кучи: Для каждого биномиального дерева в куче выполняется свойство min-кучи или max-кучи (ключ каждого узла меньше или равен ключам его потомков для min-кучи, и больше или равен для max-кучи).
Свойство биномиальной кучи: В биномиальной куче не может быть двух биномиальных деревьев одного порядка. Кроме того, биномиальные деревья в куче упорядочены по возрастанию порядка.
Операции:
MakeHeap()
: Создает пустую биномиальную кучу.
Insert(x)
: Вставляет новый элемент x
в кучу.
Создать новое биномиальное дерево, состоящее из одного узла, содержащего добавляемый элемент. Объединить биномиальную кучу с новым деревом. Если после объединения в куче появились два дерева одинаковой степени, выполните их слияние. Повторять, пока не останется деревьев одинаковой степени.
Minimum()
(для min-кучи) / Maximum()
(для max-кучи): Возвращает элемент с минимальным (максимальным) ключом.
ExtractMin()
(для min-кучи) / ExtractMax()
(для max-кучи): Извлекает и возвращает элемент с минимальным (максимальным) ключом.
Union(H1, H2)
: Объединяет две биномиальные кучи H1
и H2
в одну.
DecreaseKey(x, k)
(для min-кучи) / IncreaseKey(x, k)
(для max-кучи): Уменьшает (увеличивает) значение ключа элемента x
до k
.
Delete(x)
: Удаляет элемент x
из кучи.
Преимущества биномиальных куч:
Операция Union
выполняется за время
Остальные операции также выполняются за логарифмическое время.
Фибоначчиевы кучи (Fibonacci heaps) — это сложная, но очень эффективная структура данных для реализации очередей с приоритетами. Они обеспечивают амортизированно константное время для большинства операций, что делает их привлекательными для алгоритмов, где интенсивно используются операции с очередями с приоритетами, например, алгоритм Дейкстры для поиска кратчайших путей.
Коллекция деревьев: Фибоначчиева куча представляет собой набор неупорядоченных деревьев, каждое из которых удовлетворяет свойству min-кучи (или max-кучи).
Указатель на минимум (максимум): Куча хранит указатель на корень дерева с минимальным (максимальным) ключом.
Связанный список корней: Корни деревьев организованы в двусвязный циклический список.
Отметки узлов: Каждый узел имеет отметку (mark), которая указывает, был ли у него удален потомок с момента последнего подключения к другому дереву.
Ленивые операции: Фибоначчиевы кучи откладывают "тяжелую" работу до тех пор, пока это возможно, что позволяет амортизировать затраты на операции.
Объединение деревьев: Операция Union
выполняется просто путем объединения списков корней двух куч.
Отложенное восстановление структуры: Структура кучи восстанавливается только при извлечении минимального (максимального) элемента.
MakeHeap()
: Создает пустую фибоначчиеву кучу.
Insert(x)
: Вставляет новый элемент x
в кучу, создавая новое дерево с одним узлом. Чтобы добавить элемент в фибоначчиеву кучу, нужно:
Создать новый узел с этим элементом.
Добавить новый узел в список корней кучи, сохраняя порядок по возрастанию степени.
Объединить деревья одинаковой степени в списке корней, чтобы у каждого корня была уникальная степень.
Обновить указатель на минимальный элемент.
Minimum()
(для min-кучи) / Maximum()
(для max-кучи): Возвращает элемент с минимальным (максимальным) ключом, используя указатель на минимум (максимум).
ExtractMin()
(для min-кучи) / ExtractMax()
(для max-кучи): Извлекает и возвращает элемент с минимальным (максимальным) ключом, выполняя "тяжелую" работу по восстановлению структуры кучи.
Union(H1, H2)
: Объединяет две фибоначчиевы кучи H1
и H2
в одну, объединяя их списки корней.
DecreaseKey(x, k)
(для min-кучи) / IncreaseKey(x, k)
(для max-кучи): Уменьшает (увеличивает) значение ключа элемента x
до k
, возможно, отсоединяя узел от его родителя и добавляя его в список корней.
Delete(x)
: Удаляет элемент x
из кучи, используя DecreaseKey
(или IncreaseKey
) для уменьшения (увеличения) его ключа до ExtractMin
(или ExtractMax
).
Операция | Амортизированная сложность |
---|---|
MakeHeap , Insert , Minimum /Maximum , Union | |
ExtractMin /ExtractMax , Delete | |
DecreaseKey /IncreaseKey |
Очень быстрые операции: Большинство операций выполняются за амортизированно константное время.
Эффективность в алгоритмах графов: Фибоначчиевы кучи особенно эффективны в алгоритмах, где часто используются операции DecreaseKey
(или IncreaseKey
), например, алгоритм Дейкстры.
Считай, ответы.
Верные утверждения:
2.1 Асимптотика какого алгоритма зависит от размера алфавита - Поиск подстрок спомощью автоматов** 2.2 Какой из приведенных алгоритмов работает лучше в худшем случае - Боуера-Мура 2.3 Асимптотика какого алгоритма зависит от размера машинного слова - Поиск подстрок с помощью автоматов, Рабина-Карпа 2.4 В алгоритме Кнута-Морриса-Пратта используется - Префикс-функция для образца 2.5 Какой алгоритм использует эвристику безопасного суффикса? Буера-Мура 2.6 Какой из приведённых алгоритмов начинает проверку с конца образца? Бойера-Мура
3.1 Результатом алгоритма топологической сортировки является упорядоченный набор вершин 3.2 Результатом алгоритма Крускала является минимальное остовное дерево 3.3 Результатом алгоритма Прима является минимальное остовное дерево 3.4 Результатом работы алгоритма Дейкстры является дерево кратчайших путей
4.1 Операция вращения являются вспомогательные для AVL-деревьев, RBT-деревьев 4.2 Какой вид деревьев имеет минимальную высоту: Б-деревья 4.3 В стандартной библиотеке C++ для реализации контейнера std::map используются красно-чёрные деревья
5.1 Рассмотрение отрицательного сдвига подстроки возможно в алгоритме Боуера-Мура 5.2 Ситуация “холостое срабатывание” возможна в алгоритме Рабина-Карпа 5.3 Что даст алгоритм топологической сортировки на графах с циклами? Неверный ответ 5.4 Алгоритм топологической сортировки неприменим и даёт неверный ответ в случае, если граф содержит циклы
6.1 Если основная теорема о рекуррентных соотношениях не применима - Возможно, оценка может быть получена другими методами 6.2 Основная теорема о рекуррентных соотношениях - Позволяет в некоторых случаях найти асимптотическую оценку рекуррентного соотношения 6.3 Что из приведенного используется для оценки рекуррентных соотношений? Метод подстановки. Метод рекурсий. Метод итераций.
7.1 Эффективные операции для RBT: Извлечение корня с образованием двух RBT, Извлечение минимального элемента 7.2 Операции, которые не используются для хеш-таблиц: Объединение хеш-таблиц, извлечение минимального, изменение размера таблицы 7.3 Какие маркеры ячеек обычно реализуются в хеш-таблицах на открытой адресации? - Элемент удален, Ячейка пуста 7.4 Чем деревья поиска отличаются от хеш-таблиц? Поддержание порядка на элементах, Поддержкой постоянных итераторов 7.5 Методы std::lower_bound и std::upper_bound в C++ дают одинаковый результат в случае, если элемент в контейнере отсутствует
8.1 Структура бинарной кучи соответствует структуре RBT и AVL 8.2 Почему бинарная куча обычно не предоставляет итераторов на элементы? Это не имеет смысла — элементы не упорядочены, Положение элементов в памяти часто меняется
9.1 Какие из приведенных структур можно рассматривать как набор деревьев? Биномиальные кучи, Фибоначчиевы кучи
10.1 Какие операции поддерживаются биномиальной кучей? Извлечение минимального эл-та, слияние 2-х куч 10.2 Какой ответ даст алгоритм топологической сортировки на графах с циклами? Гарантированно неверный ответ 10.3 Какие операции поддерживаются фибоначчиевой кучей? Извлечение минимального эл-та, слияние 2-х куч 10.4 Структура бинарной кучи соответствует структуре идеально сбалансированного дерева
11.1 Будет ли работать алгоритм Прима на графах с петлями? Да, с получением верного результата 11.2 Алгоритм Прима работает обычно на взвешенных графах 11.3 Будет ли работать алгоритм Крускала на графах с петлями? Да, с получением верного результата 11.4 Могут ли алгоритмы Крускала и Прима давать разные результаты на одном графе? Только при наличии рёбер с одинаковым весом
12.1 Что из приведенного верно? (про деревья) AVL-дерево можно представить в виде RBT-дерева(раскрасив вершины), RBT-дерево не всегда является AVL-деревом 12.2 Что из приведенного верно? (про жадные алгоритмы и динамику) Применимость этих стратегий не связана напрямую 12.3 Алгоритм Прима работает обычно на взвешенных графах
13.1 Критерии применимости динамического программирования: Оптимальность по подзадачам, Повторяющиеся подзадачи 13.2 Может ли фибоначчиева куча иметь такую же структуру, что и биномиальная: Да, если не выполнять объединение куч, Да, если не извлекать произвольные элементы
14.1 Какие эвристики применяются в системах непересекающихся множеств - Объединение по рангу(весовая), Эвристика сжатия путей 14.2 Эвристика “сжатия путей” применяется в алгоритме – Крускала 14.3 Какая структура данных “откладывает” восстановление нормального вида до завершения последовательности однотипных операций - Фибоначчиевы кучи 14.3 Эвристика “по весу” применяется в алгоритме - Крускала
15.1 В системах непересекающихся мн-в обычно не реализуется пересечение мн-в, разбиение мн-в, извлечение минимального эл-та Комментарий: В системах непересекающихся множеств реализуется только объединение множеств и проверка на принадлежность (по элементу получаем представителя его множества, либо индекс), остальное не реализуется.
15.2 Укажите эффективный метод для решения задачи коммивояжере - Динамическое программирование
16.1 Амортизированная стоимость операций является усредненной оценкой стоимости операции для некоторого набора операций 16.2 Амортизированная стоимость операций является оценкой усредненной стоимости набора операций
Ссылки на места в документе, где есть ответ на соответствующий вопрос.
17.1 Дайте определение биноминальной кучи. Ссылка на ответ 17.2 Идея метода ветвей и границ на примере задачи коммивояжера. Ссылка на ответ 17.3 Укажите, какую операцию было бы неплохо добавить к очереди с приоритетами, чтобы в алгоритме Дейкстры не возникало дублирование элементов в очереди - Обновление приоритета элемента
18.1 Укажите оценки эффективности основных операций для хеш-таблицы на основе
открытой адресации - Добавление, поиск и удаление
19.1 Алгоритм Прима и оценка времени работы. Ссылка на ответ 19.2 Алгоритм Крускала и оценка времени работы. Ссылка на ответ
20.1 Алгоритм Рабина-Карпа. Ссылка на ответ 20.2 Алгоритм Кнута-Морриса-Пратта. Ссылка на ответ
21.1 Префикс-функция.
Конечный автомат для поиска подстроки. Ссылка на ответ
Мастер-теорема. Ссылка
…
24.1 Проиллюстрируйте добавление в указанное B-tree 85.
24.2
24.3
24.4 Дайте определение биноминального дерева. Ссылка на ответ
25.1 Продемонстрируйте добавление в RBT-дерево чисел от 10 до 2.
25.2 Продемонстрируйте добавление в RBT-дерево букв от A до G
25.3 Продемонстрируйте добавление в AVL-дерево букв от A до G.
25.4 Нарисуйте биномиальную кучу для 7 элементов.
26.1
26.2 Является ли указанное дерево Б-деревом, если нет – почему, если да, то каким? (степень)
27.1 Пример хеш-функции на основе умножения с квадратичной последовательностью проб.
27.2 Пример хеш-функции на основе деления с квадратичной последовательностью проб
27.3 Почему эффективность хеш-таблицы на основе открытой адресации обычно ухудшается со временем и какая операция страдает больше всего? Из-за заполнения. С увеличением количества элементов увеличивается вероятность коллизий. Это увеличивает время работы операции поиска.
28.1 Алгоритм добавления элемента в биномиальную кучу. Ссылка 28.2 Алгоритм добавления элемента в бинарную кучу. Ссылка 28.3 Алгоритм добавления элемента в фибоначчиеву кучу. Ссылка 28.4 Какое отношение должно быть реализовано для элементов чтобы их можно было размещать в структуры наподобие std::set? Реализовать < или использовать компаратор
29.1 Выполните амортизационный анализ для структуры “мультистек” (push,pop,multipop). См. что-нибудь отсюда 29.2 Что такое «Фильтр Блума», для чего используется? Ссылка 29.3 Какой тип ошибки НЕ может выдать фильтр Блума: «ложноположительное срабатывание» или «ложноотрицательное срабатывание»? ложноотрицательное срабатывание
30.1 Возможны ли ситуации, в которых алгоритм с худшей асимптотической оценкой (в среднем) будет более предпочтителен, нежели алгоритм с лучшей асимптотикой? Да возможны
30.2 Что такое ФЛОПСы (FLOPS), где и для чего они используются? Это единица измерения, показывающая, сколько операций с плавающей запятой компьютер может выполнить за одну секунду. Используется в научных вычислениях, графике, играх, ИИ.
31.1 Динамическое программирование «сверху вниз» - основная идея и схема алгоритма. 31.2 Что такое мемоизация? 31.3 Динамическое программирование "снизу вверх" - основная схема и идея алгоритма. Ссылка на ответы к 31
32.1 Укажите свойства хеш-функций, которые существенны для использования в хеш-таблицах. Равномерность, Быстродействие, Детерминированность, Минимизация коллизий, Скорость вычисления
32.2 Что означает запись