4551
правка
Модель без явного задания параметров кэша: различия между версиями
Материал из WEGA
Модель без явного задания параметров кэша (посмотреть исходный код)
Версия от 13:22, 27 февраля 2017
, 27 февраля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
Перестановка в модели ввода-вывода имеет сложность <math>\Theta (min \{ Sort(N), N \} ) \;</math> в предположении, что элементы неделимы [2]. Было доказано [16], что эта асимптотическая сложность не может быть получена в модели без явного задания параметров кэша, так что и в случае этой задачи разделение имеет место. | Перестановка в модели ввода-вывода имеет сложность <math>\Theta (min \{ Sort(N), N \} ) \;</math> в предположении, что элементы неделимы [2]. Было доказано [16], что эта асимптотическая сложность не может быть получена в модели без явного задания параметров кэша, так что и в случае этой задачи разделение имеет место. | ||
Была предложена реализация очередей с приоритетами на базе модели без явного задания параметров кэша с <math>O(1 | Была предложена реализация очередей с приоритетами на базе модели без явного задания параметров кэша с <math>O(\frac{1}{B} log_{\frac{M}{B}} \; \frac{N}{M})</math> амортизированных переносов содержимого памяти. | ||
