1313
правок
Модель без явного задания параметров кэша: различия между версиями
Материал из WEGA
Модель без явного задания параметров кэша (посмотреть исходный код)
Версия от 03:57, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 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> амортизированных переносов содержимого памяти. | ||
| Строка 126: | Строка 126: | ||
27. Vitter, J.S.: Geometric and spatial data structures in external memory. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications. CRC Press, Boca Raton (2005) | 27. Vitter, J.S.: Geometric and spatial data structures in external memory. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications. CRC Press, Boca Raton (2005) | ||
[[Категория: Совместное определение связанных терминов]] | |||
