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

Теорема доказывает, что сортировка на базе сравнения, выполняемая без явного задания параметров кэша и без предположения о высоте кэша, не может сравниться по эффективности с алгоритмами на базе модели ввода-вывода, в которой значения M и В известны алгоритму. Кроме того, из нее естественным образом следует, что если алгоритм без явного задания параметров кэша должен быть оптимальным по вводу-выводу для случая <math>B = \frac{M}{2} \;</math>, то наилучшим вариантом будет бинарная сортировка слияния: любой другой алгоритм будет также в <math>\Theta (log \; M)</math> хуже оптимальной границы количества переносов блоков для случая <math>M \gg B \;</math>.

Для родственной задачи перестановки массива следующая теорема утверждает, что для всех возможных предположений о высоте кэша B < Ms не существует алгоритма без явного задания параметров кэша с границей количества переносов блоков (даже для среднего случая), обеспечивающего нижнюю границу для наихудшего случая в модели ввода-вывода.

Теорема 2 ([4], теорема 2). Для всех 8 > 0 не существует алгоритма перестановки без явного задания параметров кэша, который для всех M >2B и 1 < B < Ms демонстрирует O(minfN; N logM/B NBg) операций ввода-вывода,усредненных по всем возможным перестановкам размера N.