4511
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Материал из WEGA
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 13:25, 18 февраля 2019
, 18 февраля 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. | ||
| Строка 18: | Строка 18: | ||
'''decrease-key'''(Q, x, k): уменьшение текущего ключа k' элемента x до k, предполагая, что k < k'. | '''decrease-key'''(Q, x, k): уменьшение текущего ключа k' элемента x до k, предполагая, что k < k'. | ||
'''meld'''(<math>Q_1, Q_2</math>): | '''meld'''(<math>Q_1, Q_2</math>): на входе очереди с приоритетами <math>Q_1</math> и <math>Q_2</math>, на выходе – очередь с приоритетом <math>Q_1 \cup Q_2</math>. | ||
Заметим, что операция delete-min может быть реализована как комбинация find-min и последующей delete, decrease-key – как delete с последующей insert, а meld – как серия find-min, delete и insert. Однако существуют и более эффективные реализации decrease-key и meld [4, 7]. | Заметим, что операция '''delete-min''' может быть реализована как комбинация '''find-min''' и последующей '''delete''', '''decrease-key''' – как '''delete''' с последующей '''insert''', а '''meld''' – как серия '''find-min''', '''delete''' и '''insert'''. Однако существуют и более эффективные реализации '''decrease-key''' и '''meld''' [4, 7]. | ||
| Строка 40: | Строка 40: | ||
Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты». | Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты». | ||
• Стандартная RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации. | • Стандартная ''пословная'' RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации. | ||
• Машина с указателями аналогична RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия. | • Машина с указателями аналогична RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия. | ||
