4519
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Перейти к навигации
Перейти к поиску
м
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 13:43, 18 февраля 2019
, 18 февраля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
Вышеприведенная редукция задает новые границы для линейных требований к объему памяти для целочисленных очередей с приоритетами, улучшая предыдущие границы, представленные в работах [8, 14] и [5], соответственно. | Вышеприведенная редукция задает новые границы для линейных требований к объему памяти для целочисленных очередей с приоритетами, улучшая предыдущие границы, представленные в работах [8, 14] и [5], соответственно. | ||
1. (Детерминированный) время обновления O(log log n) при помощи алгоритма сортировки из [9]. | 1. ('''Детерминированный случай''') время обновления O(log log n) при помощи алгоритма сортировки из [9]. | ||
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>) время обновления <math>O((log \; log \; n)^{1 + \epsilon})</math> для любого константного <math>\epsilon > 0</math> 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. ('''Строки из l слов''') ожидаемое время обновления O(l + log log n) для детерминированного и <math>O(l + \sqrt{log \; log \; n})</math> – для рандомизированного случая при помощи алгоритма сортировки строк из [10]. | ||