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

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


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




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


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


2. (Рандомизированный для стандартного алгоритма <math>AC^0</math>) ожидаемое время обновления O (log log n) при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [16].
2. (Рандомизированный для стандартного алгоритма <math>AC^0</math>) ожидаемое время обновления O(log log n) при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [16].
 
3. (Строки из l слов) ожидаемое время обновления O(l + log log n) для детерминированного и <math>O(l + \sqrt{log \; log \; n})</math> – для рандомизированного случая при помощи алгоритма сортировки строк из [10].


3. (Строки из 1 слова) ожидаемое время обновления O(l + loglog n) для детерминированного и O l + ploglog n – для рандомизированного случая при помощи алгоритма сортировки строк из [10].


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