4430
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Материал из WEGA
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 13:54, 7 февраля 2019
, 7 февраля 2019→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 123: | Строка 123: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Как упоминалось выше, комбинаторная редукция для машин с указателями, приведенная в теореме 2, является более слабой, чем редукция для пословных RAM-машин. Например, для гипотетического алгоритма сортировки с линейным временем выполнения теорема 1 предлагает очередь с приоритетами с временем обновления O(1), а теорема Theorem – с временем обновления | Как упоминалось выше, комбинаторная редукция для машин с указателями, приведенная в теореме 2, является более слабой, чем редукция для пословных RAM-машин. Например, для гипотетического алгоритма сортировки с линейным временем выполнения теорема 1 предлагает очередь с приоритетами с временем обновления O(1), а теорема Theorem – с временем обновления <math>2^{O(log^* \; n)}</math>. Остается открытым вопрос о том, можно ли устранить или уменьшить этот разрыв. | ||
== См. также == | == См. также == | ||
