4511
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Перейти к навигации
Перейти к поиску
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 14:42, 6 февраля 2019
, 6 февраля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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( | 1. (Детерминированный) время обновления O(log log n) при помощи алгоритма сортировки из [9]. | ||
2. (Рандомизированный) ожидаемое время обновления O( | 2. (Рандомизированный) ожидаемое время обновления <math>O(\sqrt{log \; log \; n})</math> при помощи алгоритма сортировки из [10]. | ||
3. (Рандомизированный с выполнением операции decrease-key за время O(1)) ожидаемое время обновления O | 3. (Рандомизированный с выполнением операции decrease-key за время O(1)) ожидаемое время обновления <math>O( (log \; n)^{\frac{1}{2 - \epsilon} )}</math> для слов длиной, больше или равной log n? и любого константного <math> \epsilon > 0</math> при помощи алгоритма сортировки из [3]. | ||