4446
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Материал из WEGA
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 14:36, 4 февраля 2019
, 4 февраля 2019→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Куча == Постановка задачи == Очередь с приоритетами предста…») |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
'''Контекст и история''' | '''Контекст и история''' | ||
Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты». | |||
• Стандартная RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся в 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации. | |||
• Машина с указателями аналогична RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия. | |||
• Класс сложности AC0 включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями AC0 понимают операции, доступные в C, такие, что функции над словами принадлежат к AC0. К примеру, в их число входит сложение, но не умножение. | |||
• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14]. | |||
• Атомарные кучи Фредмана и Уилларда [6] использовались в одной из редукций в работе [15]. Такие кучи способны поддерживать операции обновления и поиска в множествах из O(log2 n) ключей за время O(1) в худшем случае [19]. Однако атомарные кучи используют операции умножения, не принадлежащие к AC0. | |||
== Основные результаты == | |||
