Сортировка без явного задания параметров кэша: различия между версиями

Теорема 1 ([4], следствие 3). Пусть <math>B_1 = 1 \;</math> и <math>B_2 = \frac{M}{2} \;</math>. Для любого алгоритма сортировки на базе сравнения, выполняющегося без явного задания параметров кэша, примем за <math>t_1 \;</math> и <math>t_2 \;</math> верхние границы количества операций ввода-вывода, произведенных над блоками размеров <math>B_1 \;</math> и <math>B_2 \;</math>. Если для вещественного числа <math>d \ge 0 \;</math> выполняется условие <math>t_2 = d \cdot \frac{N}{B^2} \; log_{ \frac{M}{B^2} } \; \frac{N}{B^2}</math>, то <math>t_1 > \frac{1}{8} \cdot N \; log_2 \; \frac{N}{M}</math>.

Теорема доказывает, что сортировка на базе сравнения, выполняемая без явного задания параметров кэша и без предположения о высоте кэша, не может сравниться по эффективности с моделью ввода-вывода, в которой значения M и В известны алгоритму. Кроме того, из нее естественным образом следует, что если алгоритм без явного задания параметров кэша должен быть оптимальным по вводу-выводу для случая B = M/2, то наилучшим вариантом будет бинарная сортировка слияния: любой другой алгоритм будет также в @(logM) хуже оптимальной границы количества переносов блоков для случая М»В.