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

Перейти к навигации Перейти к поиску
мНет описания правки
Строка 66: Строка 66:




Редукция из теоремы 1 использует атомарные кучи [6], которые мало того что очень сложны сами по себе, но к тому же используют операции, не входящие в AC0. Следующая, несколько более слабая рекурсивная редукция, не ограничивающая область определения ключей, является полностью комбинаторной.
Редукция из теоремы 1 использует атомарные кучи [6], которые мало того что очень сложны сами по себе, но к тому же используют операции, не входящие в <math>AC^0</math>. Следующая, несколько более слабая рекурсивная редукция, не ограничивающая область определения ключей, является полностью комбинаторной.




Строка 73: Строка 73:
<math>T(n) = O(S(n) + T(log^2 \; n))</math>
<math>T(n) = O(S(n) + T(log^2 \; n))</math>


'''Редукция выполняется на машине с указателями с использованием линейного объема памяти и только стандартными операциями из <math>AC^0</math>. Обращения к значениям ключей производятся только программой сортировки.'''


Редукция выполняется на машине с указателями с использованием линейного объема памяти и только стандартными операциями из AC0. Обращения к значениям ключей производятся только программой сортировки.


Данная редукция обеспечивает следующие новые границы для очередей с приоритетами, не поддерживаемые теоремой 1, причем первые две позиции улучшают предыдущие границы, представленные в работах [13] и [16], соответственно.


Данная редукция обеспечивает следующие новые границы для очередей с приоритетами, не поддерживаемые теоремой 1, причем первые две позиции улучшают предыдущие границы, представленные в работах [  ] и [16], соответственно.
1. (Детерминированный для стандартного алгоритма класса сложности <math>AC^0</math>) время обновления O ((log log n)1+е) для любого константного e > 0 при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [10].


1. (Детерминированный для стандартного алгоритма класса сложности AC0) время обновления O ((log log n)1+е) для любого константного e > 0 при помощи стандартного алгоритма сортировки целых чисел класса AC0 из работы [10].
2. (Рандомизированный для стандартного алгоритма <math>AC^0</math>) ожидаемое время обновления O (log log n) при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [16].
 
2. (Рандомизированный для стандартного алгоритма AC0) ожидаемое время обновления O (log log n) при помощи стандартного алгоритма сортировки целых чисел класса AC0 из работы [16].


3. (Строки из 1 слова) ожидаемое время обновления O(l + loglog n) для детерминированного и O l + ploglog n – для рандомизированного случая при помощи алгоритма сортировки строк из [10].
3. (Строки из 1 слова) ожидаемое время обновления O(l + loglog n) для детерминированного и O l + ploglog n – для рандомизированного случая при помощи алгоритма сортировки строк из [10].
Источник — http://pco.iis.nsk.su/wega/index.php/Эквивалентность_между_очередями_с_приоритетами_и_сортировкой