4446
правок
Модель без явного задания параметров кэша: различия между версиями
Перейти к навигации
Перейти к поиску
Модель без явного задания параметров кэша (посмотреть исходный код)
Версия от 13:17, 27 февраля 2017
, 27 февраля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
Что касается сортировки, то фундаментальной особенностью модели ввода-вывода является то, что сортировка N элементов при помощи сравнения требует | Что касается сортировки, то фундаментальной особенностью модели ввода-вывода является то, что сортировка N элементов при помощи сравнения требует <math>\Theta (Sort(N)) \;</math> переносов содержимого памяти [2], где <math>Sort(N) = \frac{N}{B} log_{\frac{M}{B}} \; \frac{N}{M}</math>. В модели без явного задания параметров кэша сортировка может быть выполнена за <math>\Theta (Sort(N)) \;</math> переносов содержимого памяти при условии принятия так называемого ''предположения о высоте кэша'' – <math>M \ge B^{1 + \varepsilon} \;</math> [15,22]. Было показано, что выполнение этого предположения обязательно [16], что доказывает разницу в эффективности между алгоритмами без явного задания параметров кэша и алгоритмами в модели ввода-вывода (где это предположение не требуется для определения границы сортировки). | ||