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

Теорема 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>.