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

Перейти к навигации Перейти к поиску
Строка 54: Строка 54:




Теорема 1. Если для некоторой неубывающей функции S до n целочисленных ключей могут быть отсортированы за время S(n) на ключ, целочисленная очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления, т. е. вставки и удаления, за время S(n) + O(1). Здесь n равно текущему количеству ключей в очереди. Редукция использует линейный объем памяти и выполняется на стандартной пословной RAM-машине, на которой каждый целочисленный ключ хранится в одном слове.
'''Теорема 1. Если для некоторой неубывающей функции S до n целочисленных ключей могут быть отсортированы за время S(n) на ключ, целочисленная очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления, т. е. вставки и удаления, за время S(n) + O(1). Здесь n равно текущему количеству ключей в очереди. Редукция использует линейный объем памяти и выполняется на стандартной пословной RAM-машине, на которой каждый целочисленный ключ хранится в одном слове.'''




Вышеприведенная редукция задает новые границы для линейных требований к объему памяти для целочисленных очередей с приоритетами, улучшая предыдущие границы, представленные в работах [8, 14] и [5], соответственно.
Вышеприведенная редукция задает новые границы для линейных требований к объему памяти для целочисленных очередей с приоритетами, улучшая предыдущие границы, представленные в работах [8, 14] и [5], соответственно.


1. (Детерминированный) время обновления O(loglog n) при помощи алгоритма сортировки из [ ].
1. (Детерминированный) время обновления O(log log n) при помощи алгоритма сортировки из [9].


2. (Рандомизированный) ожидаемое время обновления O(loglog n) при помощи алгоритма сортировки из [10].
2. (Рандомизированный) ожидаемое время обновления <math>O(\sqrt{log \; log \; n})</math> при помощи алгоритма сортировки из [10].


3. (Рандомизированный с выполнением операции decrease-key за время O(1)) ожидаемое время обновления O I (log n) <2~e) ) для слов длиной > log n и любого константного e > 0 при помощи алгоритма сортировки из [3].
3. (Рандомизированный с выполнением операции decrease-key за время O(1)) ожидаемое время обновления <math>O( (log \; n)^{\frac{1}{2 - \epsilon} )}</math> для слов длиной, больше или равной log n? и любого константного <math> \epsilon > 0</math> при помощи алгоритма сортировки из [3].




Источник — http://pco.iis.nsk.su/wega/index.php/Эквивалентность_между_очередями_с_приоритетами_и_сортировкой