4446
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Материал из WEGA
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 14:40, 4 февраля 2019
, 4 февраля 2019→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Очередь с приоритетами представляет собой абстрактную структуру данных, поддерживающую множество из Q элементов, каждому из которых присвоено значение, называемое ключом, а также следующий набор операций [4, 7]. | ''Очередь с приоритетами'' представляет собой абстрактную структуру данных, поддерживающую множество из Q элементов, каждому из которых присвоено значение, называемое ключом, а также следующий набор операций [4, 7]. | ||
insert(Q, x, k): вставка элемента x с ключом k в Q. | '''insert'''(Q, x, k): вставка элемента x с ключом k в Q. | ||
find-min(Q): возврат элемента Q с минимальным ключом; Q не изменяется. | '''find-min'''(Q): возврат элемента Q с минимальным ключом; Q не изменяется. | ||
delete(Q, x, k): удаление элемента x с ключом k из Q. | '''delete'''(Q, x, k): удаление элемента x с ключом k из Q. | ||
Помимо этого, нередко поддерживаются также следующие операции. | Помимо этого, нередко поддерживаются также следующие операции. | ||
delete-min(Q): удаление элемента с минимальным ключом из Q и возврат измененного множества. | '''delete-min'''(Q): удаление элемента с минимальным ключом из Q и возврат измененного множества. | ||
decrease-key(Q, x, k): уменьшение текущего ключа | '''decrease-key'''(Q, x, k): уменьшение текущего ключа k' элемента x до k, предполагая, что k < k'. | ||
meld( | '''meld'''(<math>Q_1, Q_2</math>): получая на вход очереди с приоритетами <math>Q_1</math> и <math>Q_2</math>, выдает очередь с приоритетом <math>Q_1 \cup Q_2</math>. | ||
| Строка 40: | Строка 40: | ||
Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты». | Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты». | ||
• Стандартная RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся | • Стандартная RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации. | ||
• Машина с указателями аналогична RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия. | • Машина с указателями аналогична RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия. | ||
• Класс сложности | • Класс сложности <math>AC^0</math> включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями <math>AC^0</math> понимают операции, доступные в C, такие, что функции над словами принадлежат к <math>AC^0</math>. К примеру, в их число входит сложение, но не умножение. | ||
• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14]. | • Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14]. | ||
• Атомарные кучи Фредмана и Уилларда [6] использовались в одной из редукций в работе [15]. Такие кучи способны поддерживать операции обновления и поиска в множествах из O( | • Атомарные кучи Фредмана и Уилларда [6] использовались в одной из редукций в работе [15]. Такие кучи способны поддерживать операции обновления и поиска в множествах из <math>O(log^2 \; n)</math> ключей за время O(1) в худшем случае [19]. Однако атомарные кучи используют операции умножения, не принадлежащие к <math>AC^0</math>. | ||
== Основные результаты == | == Основные результаты == | ||
