4511
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Перейти к навигации
Перейти к поиску
м
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 13:38, 18 февраля 2019
, 18 февраля 2019→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
• Стандартная ''пословная'' RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации. | • Стандартная ''пословная'' RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации. | ||
• Машина с указателями аналогична RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия. | • Машина с указателями аналогична пословной RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия. | ||
• Класс сложности <math>AC^0</math> включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями <math>AC^0</math> | • Класс сложности <math>AC^0</math> включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями <math>AC^0</math> понимаются операции, доступные в C, такие, что функции над словами принадлежат к <math>AC^0</math>. К примеру, в их число входит сложение, но не умножение. | ||
• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14]. | • Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14]. | ||