Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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( (log \; n)^{\frac{1}{2 - \epsilon} ) | 3. (Рандомизированный с выполнением операции decrease-key за время O(1)) ожидаемое время обновления <math>O \Big( (log \; n)^{\frac{1}{2 - \epsilon}} \Big)</math> для слов длиной, больше или равной log n? и любого константного <math> \epsilon > 0</math> при помощи алгоритма сортировки из [3]. | ||
| Строка 69: | Строка 69: | ||
Теорема 2. Пусть дана программа сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления – за время T(n), где n – текущее количество ключей в очереди, а T(n) удовлетворяет следующему условию рекуррентности: | '''Теорема 2. Пусть дана программа сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления – за время T(n), где n – текущее количество ключей в очереди, а T(n) удовлетворяет следующему условию рекуррентности:''' | ||
<math>T(n) = O(S(n) + T(log^2 \; n))</math> | |||
Редукция выполняется на машине с указателями с использованием линейного объема памяти и только стандартными операциями из AC0. Обращения к значениям ключей производятся только программой сортировки. | Редукция выполняется на машине с указателями с использованием линейного объема памяти и только стандартными операциями из AC0. Обращения к значениям ключей производятся только программой сортировки. | ||