Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями

Перейти к навигации Перейти к поиску
Строка 42: Строка 42:
• Стандартная ''пословная'' RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации.
• Стандартная ''пословная'' RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации.


• Машина с указателями аналогична RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия.
• Машина с указателями аналогична пословной RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия.


• Класс сложности <math>AC^0</math> включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями <math>AC^0</math> понимают операции, доступные в C, такие, что функции над словами принадлежат к <math>AC^0</math>. К примеру, в их число входит сложение, но не умножение.
• Класс сложности <math>AC^0</math> включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями <math>AC^0</math> понимаются операции, доступные в C, такие, что функции над словами принадлежат к <math>AC^0</math>. К примеру, в их число входит сложение, но не умножение.


• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14].
• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14].
Источник — http://pco.iis.nsk.su/wega/index.php/Эквивалентность_между_очередями_с_приоритетами_и_сортировкой