\input style
\chapno=5\subchno=4
\chapnotrue

%%438
\htable{ЄАБЛИЦА 1}%
{їАРАКТЕРИСТИКИ ОПТИМАЛЬНОГО ДЕРЕВА $A_m(n)$, $k_m(n)$ ПРИ $\alpha=\beta=1$}%
{$n=#$\hfill&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$\hfill&$n=#$\hfill\cr
\omit
  & m=1 &  m=2 & m=3 & m=4 & m=5 & m=6 & m=7 & m=8 & m=9 & m=10& m=11& m=12& \hbox{юПИСАНИЕ ДЕРЕВА}\cr
1 &  0,0&      &     &     &     &     &     &     &     &     &     &     &-         & 1\cr
2 &  6,2&  0,1 &     &     &     &     &     &     &     &     &     &     &1:1       & 2\cr
3 & 12,3&  6,1 &  0,1&     &     &     &     &     &     &     &     &     &1:1:1     & 3\cr
4 & 20,4& 12,1 &  6,1&  0,1&     &     &     &     &     &     &     &     &1:1:1:1   & 4\cr
5 & 30,5& 18,2 & 12,1&  6,1&  0,1&     &     &     &     &     &     &     &1:1:1:1:1 & 5\cr
6 & 42,2& 24,3 & 18,1& 12,1&  6,1&  0,1&     &     &     &     &     &     & 3:3      & 6\cr
7 & 52,3& 32,3 & 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     &     & 1:3:3    & 7\cr
8 & 62,3& 40,4 & 30,2& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     & 2:3:3    & 8\cr
9 & 72,3& 50,4 & 36,3& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     & 3:3:3    & 9\cr
10& 84,3& 60,5 & 44,3& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     & 3:3:4    &10\cr
11& 96,3& 72,4 & 52,3& 42,2& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     & 3:4:4    &11\cr
12&108,3& 82,4 & 60,4& 48,3& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1& 4:4:4    &12\cr
13&121,4& 92,4 & 70,4& 56,3& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1& 3:3:3:4  &13\cr
14&134,4&102,5 & 80,4& 64,3& 54,2& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1& 3:3:4:4  &14\cr
15&147,4&114,5 & 90,5& 72,3& 60,3& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 3:4:4:4  &15\cr
16&160,4&124,7 &102,4& 80,4& 68,3& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 4:4:4:4  &16\cr
17&175,4&134,8 &112,4& 90,4& 76,3& 66,2& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 4:4:4:5  &17\cr
18&190,4&144,9 &122,4&100,4& 84,3& 72,3& 66,1& 60,1& 54,1& 48,1& 42,1& 36,1& 4:4:5:5  &18\cr
19&205,4&156,9 &132,5&110,4& 92,3& 80,3& 72,1& 66,1& 60,1& 54,1& 48,1& 42,1& 4:5:5:5  &19\cr
20&220,4&168,9 &144,4&120,5&100,4& 88,3& 78,2& 72,1& 66,1& 60,1& 54,1& 48,1& 5:5:5:5  &20\cr
21&236,5&180,9 &154,4&132,4&110,4& 96,3& 84,3& 78,1& 72,1& 66,1& 60,1& 54,1& 4:4:4:4:5&21\cr
22&252,3&192,10&164,4&142,4&120,4&104,3& 92,3& 84,1& 78,1& 72,1& 66,1& 60,1& 4:9:9    &22\cr
23&266,3&204,11&174,5&152,4&130,4&112,3&100,3& 90,2& 84,1& 78,1& 72,1& 66,1& 5:9:9    &23\cr
24&282,3&216,12&186,5&162,5&140,4&120,4&108,3& 96,3& 90,1& 84,1& 78,1& 72,1& 5:9:10   &24\cr
25&296,3&229,12&196,7&174,4&150,5&130,4&116,3&104,3& 96,1& 90,1& 84,1& 78,1& 7:9:9    &25\cr
}
эАШ ВЫВОД ВЫРАЖЕНИЯ~$(2)$ ПОКАЗЫВАЕТ, ЧТО ВСЕГДА, КОГДА ИСПОЛЬЗУЮТСЯ 
$P+1$~РАВНЫХ БУФЕРОВ, БУДЕТ ИМЕТЬ МЕСТО СООТНОШЕНИЕ~$\alpha\le\beta$. 
яРЕДЕЛЬНЫЙ СЛУЧАЙ~$\alpha=\beta$, ПОКАЗАННЫЙ В ТАБЛ.~1 И НА РИС.~93, 
ВОЗНИКАЕТ ТОГДА, КОГДА ТРЕБУЕТСЯ МИНИМИЗИРОВАТЬ САМО ВРЕМЯ ПОИСКА 
БЕЗОТНОСИТЕЛЬНО КО ВРЕМЕНИ ПЕРЕДАЧИ.

тЕРНЕМСЯ К НАШЕЙ ПЕРВОНАЧАЛЬНОЙ ЗАДАЧЕ. ьЫ ЕЩЕ НЕ РАССМОТРЕЛИ, КАК 
ПОЛУЧИТЬ НАЧАЛЬНЫЕ ОТРЕЗКИ; БЕЗ СОВМЕЩЕНИЯ ЧТЕНИЯ/ЗАПИСИ/ВЫЧИСЛЕНИЙ 
ВЫБОР С ЗАМЕЩЕНИЕМ ТЕРЯЕТ НЕКОТОРЫЕ ИЗ СВОИХ ПРЕИМУЩЕСТВ. тОЗМОЖНО, НАМ 
СЛЕДУЕТ ЗАПОЛНИТЬ ВСЮ ВНУТРЕННЮЮ
\picture{ЁИС. 93. юПТИМАЛЬНЫЙ СПОСОБ СЛИЯНИЯ 22 НАЧАЛЬНЫХ ОТРЕЗКОВ РАВНОЙ 
ДЛИНЫ, ЕСЛИ В ТЕОРЕМЕ э $\alpha=\beta$. ¤ТА СХЕМА МИНИМИЗИРУЕТ ВРЕМЯ 
ПОИСКА ПРИ ПРЕДПОЛОЖЕНИЯХ, ПРИВЕДШИХ К ФОРМУЛЕ (2).
}
ПАМЯТЬ, ОТСОРТИРОВАТЬ ЕЕ И ВЫВЕСТИ РЕЗУЛЬТАТ; КАЖДУЮ ИЗ ТАКИХ ОПЕРАЦИЙ 
ВВОДА И ВЫВОДА МОЖНО ВЫПОЛНИТЬ С ОДНИМ ПОИСКОМ. шЛИ, ВОЗМОЖНО, ЛУЧШЕ 
ИСПОЛЬЗОВАТЬ, СКАЖЕМ, 20\% ПАМЯТИ КАК КОМБИНИРОВАННЫЙ БУФЕР ВВОДА/ВЫВОДА 
И ВЫПОЛНЯТЬ ВЫБОР С ЗАМЕЩЕНИЕМ. ¤ТО ТРЕБУЕТ В ПЯТЬ РАЗ БОЛЬШЕ ПОИСКОВ 
(ДОПОЛНИТЕЛЬНО ПРИМЕРНО 60~С!), НО УМЕНЬШАЕТ ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ 
СО~100 ДО~64; УМЕНЬШЕНИЕ БУДЕТ ЕЩЕ БОЛЕЕ РЕЗКИМ, ЕСЛИ ВВОДНЫЙ ФАЙЛ УЖЕ 
ПОЧТИ УПОРЯДОЧЕН.

хСЛИ МЫ РЕШИЛИ НЕ ИСПОЛЬЗОВАТЬ ВЫБОР С ЗАМЕЩЕНИЕМ, ТО ОПТИМАЛЬНОЕ ДЕРЕВО 
ДЛЯ $S=100$, $\alpha=0.00145$, $\beta=0.01545$ 
[СМ. (2)] ОКАЗЫВАЕТСЯ ВЕСЬМА ПРОЗАИЧЕСКИМ. ¤ТО ПРОСТО 10-ПУТЕВОЕ СЛИЯНИЕ, 
ВЫПОЛНЯЕМОЕ ЗА ДВА ПРОХОДА ПО ДАННЫМ. тЫДЕЛЯЯ 30~С НА ВНУТРЕННЮЮ 
СОРТИРОВКУ (СКАЖЕМ, 100~БЫСТРЫХ СОРТИРОВОК), ПОЛУЧАЕМ, ЧТО НАЧАЛЬНЫЙ 
РАСПРЕДЕЛИТЕЛЬНЫЙ ПРОХОД, ЗАНИМАЕТ ПРИМЕРНО
$2{1\over2}$~МИН, А КАЖДЫЙ ПРОХОД СЛИЯНИЯ ЗАНИМАЕТ ПОЧТИ 5~МИН; В ИТОГЕ
ИМЕЕМ $12.4$~МИН. хСЛИ МЫ РЕШИЛИ ИСПОЛЬЗОВАТЬ ВЫБОР С ЗАМЕЩЕНИЕМ, ТО 
ОПТИМАЛЬНОЕ ДЕРЕВО ДЛЯ $S=64$ ОКАЗЫВАЕТСЯ ОДИНАКОВО НЕИНТЕРЕСНЫМ (ДВА 
ПРОХОДА 8-ПУТЕВОГО СЛИЯНИЯ); НАЧАЛЬНЫЙ РАСПРЕДЕЛИТЕЛЬНЫЙ ПРОХОД ЗАНИМАЕТ 
ПРИМЕРНО $3{1\over2}$~МИН, КАЖДЫЙ ПРОХОД СЛИЯНИЯ---ОКОЛО $4{1\over2}$~МИН, 
ОЦЕНКА ОБЩЕГО ВРЕМЕНИ СОСТАВЛЯЕТ 12.6~МИН.
%%440
тСПОМНИМ, ЧТО В ОБОИХ ЭТИХ МЕТОДАХ ФАКТИЧЕСКИ ПОЛНОСТЬЮ 
ИСКЛЮЧАЕТСЯ СОВМЕЩЕНИЕ ЧТЕНИЯ/ЗАПИСИ/ВЫЧИСЛЕНИЙ, ЧТОБЫ ИМЕТЬ БОЛЬШИЕ 
БУФЕРЫ (С ЦЕЛЬЮ УМЕНЬШЕНИЯ ВРЕМЕНИ ПОИСКА). эИ ОДНА ИЗ ЭТИХ ОЦЕНОК НЕ 
ВКЛЮЧАЕТ ВРЕМЯ, КОТОРОЕ МОЖЕТ ПОТРЕБОВАТЬСЯ ДЛЯ ОПЕРАЦИЙ КОНТРОЛЬНОГО ЧТЕНИЯ.

эА ПРАКТИКЕ ПОСЛЕДНИЙ ПРОХОД СЛИЯНИЯ ОКАЗЫВАЕТСЯ ОТЛИЧНЫМ ОТ ОСТАЛЬНЫХ; 
НАПРИМЕР, ВЫВОДНЫЕ ДАННЫЕ ЧАСТО РЕДАКТИРУЮТСЯ И/ИЛИ ЗАПИСЫВАЮТСЯ НА ЛЕНТУ.
 т ТАКИХ СЛУЧАЯХ ДЕРЕВО, ИЗОБРАЖАЮЩЕЕ СХЕМУ СЛИЯНИЯ, СЛЕДУЕТ ВЫБИРАТЬ С 
ИСПОЛЬЗОВАНИЕМ В КОРНЕВОМ УЗЛЕ ИНОГО КРИТЕРИЯ ОПТИМАЛЬНОСТИ.

\section *фРУГОЙ СПОСОБ РАСПРЕДЕЛЕНИЯ БУФЕРОВ. фАВИД~¤.~ЇЕРГЮСОН УКАЗАЛ 
[{\sl CACM,\/} {\bf 14} (1971), 476--478], ЧТО МОЖНО УМЕНЬШИТЬ 
ВРЕМЯ ПОИСКА, ЕСЛИ НЕ ДЕЛАТЬ ВСЕ БУФЕРЫ ОДНОГО РАЗМЕРА. ЄА ЖЕ МЫСЛЬ И 
ПРИМЕРНО В ТО ЖЕ ВРЕМЯ ПРИШЛА В ГОЛОВУ ЕЩЕ НЕСКОЛЬКИМ ЛИЦАМ 
[S.~J.~Waters, {\sl Comp.~J.,\/} {\bf 14} (1971), 109--112; 
Ewing~S.~Walker, Software Age, {\bf 4} (August-September, 1970), 16--17].

яРЕДПОЛОЖИМ, ЧТО МЫ ВЫПОЛНЯЕМ ЧЕТЫРЕХПУТЕВОЕ СЛИЯНИЕ ОТРЕЗКОВ РАВНОЙ 
ДЛИНЫ~$L_0$, ИМЕЯ ПАМЯТЬ В $M$~ЛИТЕР. хСЛИ МЫ РАЗДЕЛИМ ПАМЯТЬ НА РАВНЫЕ 
БУФЕРЫ РАЗМЕРА~$B=M/5$, ТО НАМ ПОТРЕБУЕТСЯ ОКОЛО $L_0/B$~ПОИСКОВ ДЛЯ 
КАЖДОГО ВВОДНОГО ФАЙЛА И $4L_0/B$~ПОИСКОВ ДЛЯ ВЫВОДА, ЧТО В СУММЕ ДАЕТ 
$8L_0/B = 40L_0/M$~ПОИСКОВ. эО ЕСЛИ МЫ ИСПОЛЬЗУЕМ ЧЕТЫРЕ БУФЕРА ВВОДА 
РАЗМЕРА~$M/6$ И ОДИН БУФЕР ВЫВОДА РАЗМЕРА~$M/3$, ТО НАМ ПОТРЕБУЕТСЯ 
ВСЕГО ЛИШЬ ОКОЛО $4\times(6L_0/M)+4\times(3L_0/M)=36L_0/M$~ПОИСКОВ! 
тРЕМЕНА ПЕРЕДАЧИ В ОБОИХ СЛУЧАЯХ ОДИНАКОВЫ, ТАК ЧТО МЫ НИЧЕГО НЕ 
ПОТЕРЯЕМ ОТ ЭТОГО ИЗМЕНЕНИЯ.

т ОБЩЕМ СЛУЧАЕ ПРЕДПОЛОЖИМ, ЧТО МЫ ХОТИМ СЛИТЬ ОТСОРТИРОВАННЫЕ ФАЙЛЫ, 
ИМЕЮЩИЕ ДЛИНЫ~$L_0$,~\dots, $L_p$, В ОТСОРТИРОВАННЫЙ ФАЙЛ 
ДЛИНЫ~$L_{P+1}=L_1+\cdots+L_P$, И ПРЕДПОЛОЖИМ, ЧТО ДЛЯ $k\hbox{-ГО}$ФАЙЛА 
ИСПОЛЬЗУЕТСЯ БУФЕР РАЗМЕРА~$B_k$. ЄОГДА
$$
B_1+\cdots+B_P+B_{P+1}=M,
\eqno(6)
$$
ГДЕ $M$---ОБЩИЙ ОБоЕМ НАЛИЧНОЙ ВНУТРЕННЕЙ ПАМЯТИ. ўИСЛО ПОИСКОВ БУДЕТ 
ПРИБЛИЗИТЕЛЬНО РАВНО
$$
{L_1\over B_1}+\cdots+{L_P\over B_P}+{L_{P+1}\over B_{P+1}}.
\eqno(7)
$$
яОПЫТАЕМСЯ МИНИМИЗИРОВАТЬ ЭТУ ВЕЛИЧИНУ ПРИ УСЛОВИИ~(6), СЧИТАЯ ДЛЯ 
УДОБСТВА, ЧТО $B_k$ НЕ ОБЯЗАНЫ БЫТЬ ЦЕЛЫМИ. хСЛИ УВЕЛИЧИТЬ~$B_j$ 
НА~$\delta$ И УМЕНЬШИТЬ~$B_k$ НА ТУ ЖЕ НЕБОЛЬШУЮ ВЕЛИЧИНУ, ТО ЧИСЛО 
ПОИСКОВ ИЗМЕНИТСЯ НА
$$
{L_j\over B_j+\delta}-{L_j\over B_j}+{L_k\over B_k-\delta}-{L_k\over B_k} 
=\left({L_k\over B_k(B_k-\delta)}-{L_j\over B_j(B_j+\delta)}\right)\delta,
$$
Т.~Е., РАСПРЕДЕЛЕНИЕ МОЖНО УЛУЧШИТЬ, ЕСЛИ $L_j/B^2_j\ne L_k/B^2_k$. 
ёЛЕДОВАТЕЛЬНО,
%% 441
МЫ ПОЛУЧИМ МИНИМАЛЬНОЕ ЧИСЛО ПОИСКОВ, ТОЛЬКО ЕСЛИ
$$
{L_1\over B^2_1}=\cdots={L_P\over B^2_P}={L_{P+1}\over B^2_{P+1}}.
\eqno(8)
$$
ЄАК КАК МИНИМУМ ОБЯЗАТЕЛЬНО СУЩЕСТВУЕТ, ОН ДОЛЖЕН ДОСТИГАТЬСЯ ПРИ
$$
B_k=\sqrt{L_k}M/(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}}),\quad 1\le k\le P+1,
\eqno(9)
$$
ПОСКОЛЬКУ ЭТО ЕДИНСТВЕННЫЕ ЗНАЧЕНИЯ~$B_1$,~\dots, $B_{P+1}$, 
УДОВЛЕТВОРЯЮЩИЕ ОДНОВРЕМЕННО~(6) И~(8). яОДСТАНОВКА ЭТИХ ЗНАЧЕНИЙ 
В~(7) ДАЕТ ВЕСЬМА ПРОСТУЮ ФОРМУЛУ ДЛЯ ОБЩЕГО ЧИСЛА ПОИСКОВ:
$$
(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}})^2/M,
\eqno(10)
$$
КОТОРУЮ МОЖНО СРАВНИТЬ С ЧИСЛОМ $(P+1)(L_1+\cdots+L_{P+1})/M$,
 ПОЛУЧАЮЩИМСЯ В ТОМ СЛУЧАЕ, ЕСЛИ ВСЕ БУФЕРЫ РАВНЫ ПО ДЛИНЕ.
тЫИГРЫШ РАВЕН~$\sum_{1\le j<k\le P+1}(\sqrt{L_j}-\sqrt{L_k})^2/M$   
СОГЛАСНО УПР.~1.2.3-31. ъ СОЖАЛЕНИЮ, ФОРМУЛА (10) НЕ ГОДИТСЯ ДЛЯ ПРОСТОГО 
ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ СХЕМЫ СЛИЯНИЯ, КАК В ТЕОРЕМЕ~K (СР.~С УПР.~14).

\section фОПОЛНИТЕЛЬНЫЕ СООБРАЖЕНИЯ. хСЛИ ИСПОЛЬЗУЮТСЯ ДВА 
ДИСКОВЫХ УСТРОЙСТВА (ОДНО ДЛЯ ЧТЕНИЯ И ОДНО ДЛЯ ЗАПИСИ), ТО МОЖНО 
СОВМЕСТИТЬ ЧАСТЬ ВРЕМЕНИ ЗАПИСИ ЦЕНОЙ ДОПОЛНИТЕЛЬНОГО БУФЕРА ВЫВОДА. 
хСЛИ ИСПОЛЬЗУЕТСЯ МЕТОД "ПРОГНОЗИРОВАНИЯ" (Т.~Е.~МЫ СМОТРИМ НА ПОСЛЕДНИЙ 
КЛЮЧ В КАЖДОМ БУФЕРЕ ВВОДА, ЧТОБЫ ОПРЕДЕЛИТЬ, КАКОЙ БУФЕР ПЕРВЫМ 
ОСВОБОДИТСЯ), ТО МОЖНО СОВМЕСТИТЬ ЧАСТЬ ВРЕМЕНИ ЧТЕНИЯ. ъ СОЖАЛЕНИЮ, 
ПРОСТАЯ ПРОЦЕДУРА СИНХРОНИЗАЦИИ, ВРОДЕ ПРОЦЕДУРЫ В АЛГОРИТМЕ 5.4.6F, НЕ 
ОБЕСПЕЧИВАЕТ НЕПРЕРЫВНОГО ВВОДА/ВЫВОДА, ТАК КАК МЕНЯЮЩЕЕСЯ ВРЕМЯ 
ЧТЕНИЯ ОЗНАЧАЕТ, ЧТО ОПЕРАЦИИ ВВОДА И ВЫВОДА НЕ БУДУТ ОКАНЧИВАТЬСЯ В ОДНО 
ВРЕМЯ. ЄОЧНЫЙ ОБоЕМ СОВМЕЩЕНИЙ ТРУДНО ОЦЕНИТЬ, И, ВОЗМОЖНО, ЛУЧШЕ 
ПРОМОДЕЛИРОВАТЬ ПРОЦЕСС СЛИЯНИЯ, ЧТОБЫ НАЙТИ КОНСТАНТЫ~$\alpha$ И~$\beta$ 
ДЛЯ ПРИБЛИЖЕННОГО ВРЕМЕНИ СЛИЯНИЯ, КАК В ТЕОРЕМЕ~H.

хСЛИ МЫ ИСПОЛЬЗУЕМ "ПЛАВАЮЩИЕ" БУФЕРЫ (НЕ ПРИПИСАННЫЕ К КОНКРЕТНОМУ ФАЙЛУ),
 ТО ОНИ ДОЛЖНЫ БЫТЬ ОДНОГО РАЗМЕРА, И ТОГДА НЕЛЬЗЯ ПРИМЕНЯТЬ ПРИВЕДЕННУЮ 
ВЫШЕ ТЕХНИКУ РАСПРЕДЕЛЕНИЯ БУФЕРОВ; МОЖНО ТОЛЬКО ВЫБРАТЬ БУФЕРЫ ВЫВОДА 
БОЛЬШЕ, ЧЕМ БУФЕРЫ ВВОДА. хСЛИ ИСПОЛЬЗУЕТСЯ $2P$~БУФЕРОВ ВВОДА 
(ВМЕСТО~$P$), МЫ СОВМЕЩАЕМ ЗНАЧИТЕЛЬНУЮ ДОЛЮ ВРЕМЕНИ ВВОДА, ОДНАКО 
УДВАИВАЕМ ВРЕМЯ ПОИСКА И, ВОЗМОЖНО, НИЧЕГО НЕ ВЫИГРАЕМ; ПО-ВИДИМОМУ, 
ЛУЧШЕ ВСЕГО ИМЕТЬ $P+1$ ИЛИ $P+2$~БУФЕРОВ ВВОДА.
ЄЕПЕРЬ ЧИТАТЕЛЮ ДОЛЖНО БЫТЬ ЯСНО, ЧТО НИКАКОЙ ЧЕТКОЙ СТРАТЕГИИ ДЛЯ 
ОПТИМАЛЬНОЙ СОРТИРОВКИ НА ДИСКАХ НЕ РАЗРАБОТАНО;
ЧИСЛО ВОЗМОЖНЫХ ВАРИАНТОВ ЗНАЧИТЕЛЬНО ПРЕВЫШАЕТ ЧИСЛО СТРАТЕГИЙ. КОТОРЫЕ 
БЫЛИ ПРОАНАЛИЗИРОВАНЫ ТЕОРЕТИЧЕСКИ. їОТЯ ТЕОРИЯ,
%%442
РАЗВИТАЯ В ЭТОМ ПУНКТЕ, ДАЕТ НЕКОТОРЫЕ ПОЛЕЗНЫЕ ПРЕДСТАВЛЕНИЯ, ВСЕ 
ЕЩЕ ТРЕБУЕТСЯ ЗНАЧИТЕЛЬНЫЙ ОБоЕМ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ.

\section *яОДРОБНЕЕ ОБ ОПТИМАЛЬНЫХ ДЕРЕВЬЯХ. т ТЕОРЕМАХ~H И~K ИНТЕРЕСНО 
РАССМОТРЕТЬ КРАЙНИЙ СЛУЧАЙ~$\beta=0$, НЕСМОТРЯ НА ТО ЧТО ПРАКТИЧЕСКИЕ 
СИТУАЦИИ ОБЫЧНО ПРИВОДЯТ К ПАРАМЕТРАМ~$0\le\alpha\le\beta$. ъАКОЕ ДЕРЕВО С 
$n$~ЛИСТЬЯМИ ИМЕЕТ НАИМЕНЬШУЮ ВОЗМОЖНУЮ ДЛИНУ СТЕПЕННОГО ПУТИ? ыЮБОПЫТНО, 
ЧТО В ЭТОМ СЛУЧАЕ НАИЛУЧШИМ ОКАЗЫВАЕТСЯ ТРЕХПУТЕВОЕ СЛИЯНИЕ.

\proclaim ЄЕОРЕМА L. фЛИНА СТЕПЕННОГО ПУТИ ДЕРЕВА С $n$~ЛИСТЬЯМИ НИКОГДА 
НЕ МЕНЬШЕ, ЧЕМ
$$
f(n)=\cases{
3qn+2(n-3^q), & ЕСЛИ $2\cdot 3^{q-1}\le n\le 3^q$;\cr
3qn+4(n-3^q), & ЕСЛИ $3^q\le n\le 2\cdot 3^q$.\cr
}
\eqno(11)
$$
ЄЕРНАРНЫЕ ДЕРЕВЬЯ~$\cJ_n$, ОПРЕДЕЛЕННЫЕ ПРАВИЛАМИ
\picture{ЁИСУНОК НА СТР. 442}
ИМЕЮТ МИНИМАЛЬНУЮ ДЛИНУ СТЕПЕННОГО ПУТИ.

\proof. тАЖНО ЗАМЕТИТЬ, ЧТО $f (n)$---ВЫПУКЛАЯ ФУНКЦИЯ, Т. Е.
$$
f(n+1)-f(n)\ge f(n)-f(n-1) \rem{ПРИ ВСЕХ $n\ge2$}.
\eqno(13)
$$
¤ТО СВОЙСТВО СУЩЕСТВЕННО ВВИДУ СЛЕДУЮЩЕЙ ЛЕММЫ.

\proclaim ыЕММА ё. ФУНКЦИЯ~$g(n)$, ОПРЕДЕЛЕННАЯ НА ПОЛОЖИТЕЛЬНЫХ ЦЕЛЫХ 
ЧИСЛАХ, УДОВЛЕТВОРЯЕТ УСЛОВИЮ
$$
\min_{1\le k\le n} (g(k)+g(n-k))=g(\floor{n/2})+g(\ceil{n/2}), 
\quad n\ge 2,
\eqno (14)
$$
ТОГДА И ТОЛЬКО ТОГДА, КОГДА ОНА ВЫПУКЛАЯ.

\proof. хСЛИ $g(n+1)-g(n)<g(n)- g(n-1)$ ПРИ НЕКОТОРОМ~$n>2$, ТО ИМЕЕМ 
$g(n+1)+g(n-1)<g(n)+g(n)$, ЧТО ПРОТИВОРЕЧИТ~(14). юБРАТНО, ЕСЛИ~(13) 
ИМЕЕТ МЕСТО ДЛЯ~$g$ 
И~$1\le k<n-k$, ТО В СИЛУ 
ВЫПУКЛОСТИ~$g(k+1)+g(n-k-1)\le g(k)+g(n-k)$.\proofend

яОСЛЕДНЮЮ ЧАСТЬ ДОКАЗАТЕЛЬСТВА ЛЕММЫ ё МОЖНО РАСПРОСТРАНИТЬ НА 
ЛЮБОЕ~$m\ge2$ И ПОКАЗАТЬ, ЧТО
$$
\min_{n_1+\cdots+n_m=n\atop n_1, \ldots, n_m\ge 1}
 (g(n_1)+\cdots+g(n_m))=g(\floor{n/m})+g(\floor{(n+1)/m})+\cdots
+g(\floor{(n+m-1)/m}),
\eqno(15)
$$
%%443
ЕСЛИ $g$~ВЫПУКЛА. яУСТЬ
$$
f_m(n)=f(\floor{n/m})+f(\floor{(n+1)/m})+\cdots+f(\floor{(n+m-1)/m}).
$$
фОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~L ЗАВЕРШАЕТСЯ ДОКАЗАТЕЛЬСТВОМ ТОГО, 
ЧТО $f_3(n)+3n=f(n)$ И~$f_m(n)+mn\ge f(n)$ ПРИ ВСЕХ~$m\ge2$ (СМ.~УПР.~11).\proofend

сЫЛО БЫ ОЧЕНЬ ХОРОШО, ЕСЛИ БЫ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ВСЕГДА ХАРАКТЕРИЗОВАЛИСЬ 
ТАК ЖЕ ЧЕТКО, КАК В ТЕОРЕМЕ~L. эО РЕЗУЛЬТАТЫ ДЛЯ $\alpha=\beta$, КОТОРЫЕ 
МЫ ВИДИМ В ТАБЛ.~1, ПОКАЗЫВАЮТ, ЧТО ФУНКЦИЯ~$A_1(n)$ НЕ ВСЕГДА ВЫПУКЛА. эА 
САМОМ ДЕЛЕ ТАБЛ.~1 ДОСТАТОЧНО, ЧТОБЫ ОПРОВЕРГНУТЬ БОЛЬШИНСТВО ПРОСТЫХ 
ПРЕДПОЛОЖЕНИЙ ОБ ОПТИМАЛЬНЫХ ДЕРЕВЬЯХ! ьЫ, ОДНАКО, МОЖЕМ СПАСТИ ЧАСТЬ 
ТЕОРЕМЫ~L ДЛЯ СЛУЧАЯ ПРОИЗВОЛЬНЫХ~$\alpha$ И~$\beta$. ь.~°ЛЮМБЕРГЕР 
И ц.~тИЙЕМАН ПОКАЗАЛИ, ЧТО \emph{ВЫСОКИХ} ПОРЯДКОВ СЛИЯНИЯ ВСЕГДА МОЖНО 
ИЗБЕЖАТЬ.

\proclaim ЄЕОРЕМА M. хСЛИ ДАНЫ~$\alpha$ И~$\beta$, КАК В ТЕОРЕМЕ~H, ТО 
СУЩЕСТВУЕТ ОПТИМАЛЬНОЕ ДЕРЕВО, В КОТОРОМ СТЕПЕНЬ ЛЮБОГО УЗЛА НЕ ПРЕВОСХОДИТ
$$
d(\alpha, \beta)=\ceil{\min_{k\ge1}\left(k+\left(1+{1\over k}\right)
\left(1+{\beta\over\alpha}\right)\right)}.
\eqno(17)
$$

\proof. яУСТЬ $n_1$,~\dots, $n_m$---ПОЛОЖИТЕЛЬНЫЕ ЦЕЛЫЕ ЧИСЛА, ТАКИЕ, ЧТО 
$n_1+\cdots+n_m=n$, $A(n_1)+\cdots+A(n_m)= A_m(n)$, 
$n_1\le \ldots \le n_m$, И ПРЕДПОЛОЖИМ, ЧТО $m\ge d(\alpha, \beta)+1$. 
яУСТЬ $k$---ТО ЗНАЧЕНИЕ, ПРИ КОТОРОМ ДОСТИГАЕТСЯ МИНИМУМ В (17); ПОКАЖЕМ, ЧТО
$$
\alpha n(m-k)+\beta n+A_{m-k}(n)\le \alpha m n +\beta n+A_m(n),
\eqno(18)
$$
И, СЛЕДОВАТЕЛЬНО, МИНИМУМ В (4) ВСЕГДА ДОСТИГАЕТСЯ ПРИ НЕКОТОРОМ
$m\le d(\alpha, \beta)$.

яО ОПРЕДЕЛЕНИЮ, ПОСКОЛЬКУ $m\ge k+2$, МЫ ДОЛЖНЫ ИМЕТЬ
$$
\eqalign{
A_{m-k}(n) &\le A_1(n_1+\cdots+n_{k+1})+A_1(n_{k+2})+\cdots
+A_1(n_m)\le\cr
&\le \alpha(n_1+\cdots+n_{k+1})(k+1)+\beta(n_1+\cdots+n_{k+1})+\cr
&\phantom{\le}+A_1(n_1)+\cdots+A_1(n_m)=\cr
&=(\alpha(k+1)+\beta)(n_1+\cdots+n_{k+1})+A_m(n)\le\cr
&\le(\alpha(k+1)+\beta)(k+1)n/m+A_m(n),\cr
}
$$
ОТСЮДА (18) ЛЕГКО ВЫВОДИТСЯ. (ЄЩАТЕЛЬНОЕ РАССМОТРЕНИЕ ЭТОГО 
ДОКАЗАТЕЛЬСТВА ПОКАЗЫВАЕТ, ЧТО ОЦЕНКА~(17) ЯВЛЯЕТСЯ "НАИЛУЧШЕЙ ИЗ 
ВОЗМОЖНЫХ" В ТОМ СМЫСЛЕ, ЧТО НЕКОТОРЫЕ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ДОЛЖНЫ ИМЕТЬ 
УЗЛЫ СТЕПЕНИ~$d(\alpha, \beta)$; СМ. УПР.~13.) \proofend

яОСТРОЕНИЕ В ТЕОРЕМЕ~K ТРЕБУЕТ $O(N^2)$~ЯЧЕЕК ПАМЯТИ И $O(N^2\log 
N)$~ШАГОВ ДЛЯ ВЫЧИСЛЕНИЯ $A_m(n)$ ПРИ $1\le m\le n\le N$, a
%%444
В ТЕОРЕМЕ~M ПОКАЗАНО, ЧТО ТРЕБУЕТСЯ ТОЛЬКО $O(N)$~ЯЧЕЕК И $O(N^2)$~ШАГОВ. 
°ЛЮМБЕРГЕР И тИЙЕМАН ОТКРЫЛИ ЕЩЕ НЕСКОЛЬКО ОЧЕНЬ ИНТЕРЕСНЫХ СВОЙСТВ 
ОПТИМАЛЬНЫХ ДЕРЕВЬЕВ 
[Optimal disk merge patterns, {\sl Acta Informatica,\/} {\bf 3} (1973), 25--36].

\section шСПОЛЬЗОВАНИЕ СЦЕПЛЕНИЯ. ь. р. уОТЦ 
[{\sl CACM,\/} {\bf 6} (1963), 245--248]
ПРЕДЛОЖИЛ ИНТЕРЕСНЫЙ СПОСОБ, ПРИ КОТОРОМ ОТДЕЛЬНЫЕ ДОРОЖКИ СВЯЗЫВАЮТСЯ 
ВМЕСТЕ И БЛАГОДАРЯ ЭТОМУ ИСКЛЮЧАЕТСЯ ПОИСК ПРИ ВЫВОДЕ. фЛЯ РЕАЛИЗАЦИИ ЕГО 
ИДЕИ ТРЕБУЕТСЯ ПОЧТИ НЕВООБРАЗИМЫЙ НАБОР ПРОГРАММ, УПРАВЛЯЮЩИХ ДИСКАМИ, 
НО САМА ИДЕЯ, КРОМЕ СОРТИРОВКИ, ПРИМЕНИМА ВО МНОГИХ ДРУГИХ ЗАДАЧАХ, И 
ПОЭТОМУ ОНА МОЖЕТ ПРИВЕСТИ К ВЕСЬМА ЦЕННЫМ МЕТОДАМ ОБЩЕГО НАЗНАЧЕНИЯ.

шДЕЯ ПРОСТА. тМЕСТО РАЗМЕЩЕНИЯ ДОРОЖЕК ПОСЛЕДОВАТЕЛЬНО ВНУТРИ ЦИЛИНДРОВ 
ДИСКА МЫ СВЯЗЫВАЕМ ИХ ВМЕСТЕ И ХРАНИМ СПИСКИ СВОБОДНОГО ПРОСТРАНСТВА ПО 
ОДНОМУ ДЛЯ КАЖДОГО ЦИЛИНДРА. ъОГДА ПРИХОДИТ ВРЕМЯ ВЫВЕСТИ ДОРОЖКУ 
ИНФОРМАЦИИ, МЫ ЗАПИСЫВАЕМ ЕЕ В ТЕКУЩИЙ ЦИЛИНДР (В ТОТ, ГДЕ ОКАЗАЛСЯ 
ДЕРЖАТЕЛЬ ГОЛОВОК), ЕСЛИ ЭТОТ ЦИЛИНДР НЕ ПОЛОН. яРИ ЭТОМ ВРЕМЯ 
ПОИСКА ОБЫЧНО СВОДИТСЯ НА НЕТ.

чДЕСЬ НАС ПОДСТЕРЕГАЕТ ЛОВУШКА. фЕЛО В ТОМ, ЧТО МЫ НЕ МОЖЕМ ЗАПИСЫВАТЬ 
ССЫЛКУ НА СЛЕДУЮЩУЮ ДОРОЖКУ ВНУТРИ САМОЙ ДОРОЖКИ, ПОСКОЛЬКУ НЕОБХОДИМАЯ 
ДЛЯ ЭТОГО ИНФОРМАЦИЯ В НУЖНЫЙ МОМЕНТ НЕ ИЗВЕСТНА. (ьЫ МОГЛИ БЫ, ЕСЛИ ЭТО 
НАС УСТРОИТ, ЗАПИСЫВАТЬ ССЫЛКУ НА ПРЕДЫДУЩУЮ ДОРОЖКУ И НА 
СЛЕДУЮЩЕМ ПРОХОДЕ ЧИТАТЬ ФАЙЛ В ОБРАТНОМ НАПРАВЛЕНИИ.) ьОЖНО 
ХРАНИТЬ ОТДЕЛЬНУЮ ТАБЛИЦУ АДРЕСОВ СВЯЗИ ДЛЯ ДОРОЖЕК КАЖДОГО ФАЙЛА,
 ВОЗМОЖНО, ЧАСТИЧНО НА САМОМ ДИСКЕ. ёПИСКИ СВОБОДНОГО-ПРОСТРАНСТВА МОЖНО 
КОМПАКТНО ПРЕДСТАВИТЬ С ПОМОЩЬЮ БИТОВЫХ ТАБЛИЦ, ГДЕ 1000~БИТОВ УКАЗЫВАЮТ 
ЗАНЯТОСТЬ ИЛИ НЕЗАНЯТОСТЬ 1000~ДОРОЖЕК.

\qsection яОМОЖЕТ ЛИ СОРТИРОВКА КЛЮЧЕЙ? хСЛИ ЗАПИСИ ДЛИННЫЕ, А КЛЮЧИ 
КОРОТКИЕ, ВЕСЬМА ЗАМАНЧИВО СОЗДАТЬ НОВЫЙ ФАЙЛ, СОСТОЯЩИЙ ТОЛЬКО ИЗ КЛЮЧЕЙ 
ВМЕСТЕ С ПОРЯДКОВЫМИ НОМЕРАМИ, ОПРЕДЕЛЯЮЩИМИ ИХ ПЕРВОНАЧАЛЬНОЕ ПОЛОЖЕНИЕ В 
ФАЙЛЕ. яОСЛЕ СОРТИРОВКИ ЭТОГО ФАЙЛА КЛЮЧЕЙ МОЖНО ЗАМЕНИТЬ КЛЮЧИ 
ПОСЛЕДОВАТЕЛЬНЫМИ ЧИСЛАМИ~$1$, $2$,~\dots. чАТЕМ ЭТОТ НОВЫЙ ФАЙЛ МОЖНО 
ОТСОРТИРОВАТЬ ПО ПОЛОЖЕНИЮ В ПЕРВОНАЧАЛЬНОМ ФАЙЛЕ, И МЫ ПОЛУЧИМ 
УДОБНОЕ ОПИСАНИЕ ТОГО, КАК "РАСТАСОВАТЬ" ЗАПИСИ, ЧТОБЫ ПЕРЕРАЗМЕСТИТЬ ИХ В 
ТРЕБУЕМОМ ПОРЯДКЕ.

ёХЕМАТИЧЕСКИ ПРЕДСТАВИМ ПРОЦЕСС ТАК:
\halign{
#\hfill&#\hfill\cr
a) ИСХОДНЫЙ ФАЙЛ           & $(K_1, I_1)$ $(K_2, I_2)$ \dots $(K_N, I_N)$ ДЛИННЫЙ;\cr
b) КЛЮЧЕВОЙ ФАЙЛ          & $(K_1, 1)$ $(K_2, 2)$ \dots $(K_N, N)$ КОРОТКИЙ;\cr
c) ОТСОРТИРОВАННЫЙ (b)& $(K_{p_1}, p_1)$ $(K_{p_2}, p_2)$\dots $(K_{p_N}, p_N)$ КОРОТКИЙ;\cr
%%445
d) ОТРЕДАКТИРОВАННЫЙ (С) & $(1, p_1)$ $(2, p_2)$ \dots $(N, p_N)$ КОРОТКИЙ;\cr
e) ОТСОРТИРОВАННЫЙ   (d)&  $(q_1, 1)$ $(q_2, 2)$ \dots $(q_N, N)$ КОРОТКИЙ;\cr
f) ОТРЕДАКТИРОВАННЫЙ (a) & $(q_1, I_1)$  $(q_2, I_2)$ \dots $(q_N, I_n)$ ДЛИННЫЙ.\cr
}

\noindent чДЕСЬ $p_j=k$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА $q_k=j$; ДВА 
ПРОЦЕССА СОРТИРОВКИ В СТАДИЯХ (c) И (c) СРАВНИТЕЛЬНО БЫСТРЫЕ (ИНОГДА МОЖНО 
ОБОЙТИСЬ ВНУТРЕННЕЙ СОРТИРОВКОЙ), ТАК КАК ЗАПИСИ НЕ СЛИШКОМ ДЛИННЫЕ. эА 
СТАДИИ (f) МЫ СВЕЛИ ЗАДАЧУ К СОРТИРОВКЕ ФАЙЛА, КЛЮЧИ КОТОРОГО---ПРОСТО ЧИСЛА 
$\{1, 2,~\ldots, N\}$; КАЖДАЯ ЗАПИСЬ ТЕПЕРЬ ОПРЕДЕЛЯЕТ В ТОЧНОСТИ ТО МЕСТО,
КУДА ЕЕ СЛЕДУЕТ ПЕРЕМЕСТИТЬ.

яРОБЛЕМА ВНЕШНЕГО ПЕРЕРАЗМЕЩЕНИЯ, ОСТАЮЩАЯСЯ ПОСЛЕ СТАДИИ (f), КАЖЕТСЯ 
НА ПЕРВЫЙ ВЗГЛЯД ТРИВИАЛЬНОЙ, НО ФАКТИЧЕСКИ ОНА ОЧЕНЬ СЛОЖНА, И ВСЕ ЕЩЕ НЕ 
НАЙДЕНО НИ ОДНОГО ДЕЙСТВИТЕЛЬНО ХОРОШЕГО АЛГОРИТМА (СУЩЕСТВЕННО ЛУЧШЕГО, 
ЧЕМ СОРТИРОВКА). ьЫ, ОЧЕВИДНО, МОГЛИ БЫ ВЫПОЛНИТЬ ПЕРЕРАЗМЕЩЕНИЕ ЗА 
$N$~ШАГОВ, ПЕРЕМЕЩАЯ ВСЯКИЙ РАЗ ПО ОДНОЙ ЗАПИСИ; ДЛЯ 
ДОСТАТОЧНО БОЛЬШОГО~$N$ ЭТО ЛУЧШЕ, ЧЕМ $N\log N$ В МЕТОДАХ СОРТИРОВКИ. 
эО $N$ НИКОГДА НЕ БЫВАЕТ ТАКИМ БОЛЬШИМ; $N$ ПОИСКОВ ПРОСТО НЕРЕАЛЬНЫ!

ъ ОТРЕДАКТИРОВАННЫМ ЗАПИСЯМ МОЖНО ЭФФЕКТИВНО ПРИМЕНЯТЬ КАКОЙ-ЛИБО МЕТОД 
ПОРАЗРЯДНОЙ СОРТИРОВКИ, ТАК КАК КЛЮЧИ ИМЕЮТ СТРОГО РАВНОМЕРНОЕ 
РАСПРЕДЕЛЕНИЕ. эА МНОГИХ ВЫСОКОСКОРОСТНЫХ ¤ть С ВЫСОКОСКОРОСТНЫМИ 
ПЕРИФЕРИЙНЫМИ УСТРОЙСТВАМИ ВРЕМЯ ВЫЧИСЛЕНИЙ ДЛЯ ВОСЬМИПУТЕВОГО 
РАСПРЕДЕЛЕНИЯ ЗНАЧИТЕЛЬНО МЕНЬШЕ, ЧЕМ ВРЕМЯ ВЫЧИСЛЕНИЙ ДЛЯ 
ВОСЬМИПУТЕВОГО СЛИЯНИЯ; СЛЕДОВАТЕЛЬНО, РАСПРЕДЕЛИТЕЛЬНАЯ СОРТИРОВКА 
МОЖЕТ БЫТЬ НАИЛУЧШЕЙ ИЗ ВСЕХ ПРОЦЕДУР (СМ.~П.~5.4.7, А ТАКЖЕ УПР.~17).

эО, ПО-ВИДИМОМУ, БЕССМЫСЛЕННО ПРОВОДИТЬ СОРТИРОВКУ КЛЮЧЕЙ ЛИШЬ ДЛЯ ТОГО,
 ЧТОБЫ ВЫПОЛНИТЬ ЗАТЕМ ПОЛНУЮ СОРТИРОВКУ! юДНА ИЗ ПРИЧИН НЕОЖИДАННОЙ 
ТРУДНОСТИ ПРОБЛЕМЫ ВНЕШНЕГО ПЕРЕРАЗМЕЩЕНИЯ БЫЛА ОТКРЫТА Ё.~є.~ЇЛОЙДОМ, 
КОТОРЫЙ НАШЕЛ НЕТРИВИАЛЬНУЮ НИЖНЮЮ ГРАНИЦУ ДЛЯ ЧИСЛА ПОИСКОВ, ТРЕБУЕМЫХ,
 ЧТОБЫ ПЕРЕСТАВИТЬ ЗАПИСИ В ДИСКОВОМ ФАЙЛЕ 
[Complexity of Computer Computations (New York, Plenum, 1972), 105--109].

ЁЕЗУЛЬТАТ ЇЛОЙДА УДОБНО ОПИСАТЬ, ВОСПОЛЬЗОВАВШИСЬ АНАЛОГИЕЙ С ЛИФТОМ, 
КАК В П.~5.4.8; НА ЭТОТ РАЗ МЫ ХОТИМ НАЙТИ ГРАФИК РАБОТЫ ЛИФТА, 
МИНИМИЗИРУЮЩИЙ ЧИСЛО ОСТАНОВОК, А НЕ ПРОЙДЕННОЕ РАССТОЯНИЕ. (ьИНИМИЗАЦИЯ 
ЧИСЛА \emph{ОСТАНОВОК} НЕ ВПОЛНЕ ЭКВИВАЛЕНТНА НАХОЖДЕНИЮ АЛГОРИТМА 
ПЕРЕРАЗМЕЩЕНИЯ С МИНИМАЛЬНЫМ ЧИСЛОМ ПОИСКОВ, ТАК КАК ОДНА ОСТАНОВКА 
ОБоЕДИНЯЕТ ВХОД В ЛИФТ С ВЫХОДОМ ИЗ НЕГО; ОДНАКО РАЗНИЦА НЕ СЛИШКОМ ВЕЛИКА,
  И МЫ ВОСПОЛЬЗУЕМСЯ КРИТЕРИЕМ МИНИМИЗАЦИИ ОСТАНОВОК, ЧТОБЫ ПОЯСНИТЬ 
ОСНОВНЫЕ ИДЕИ.)
%% 446
сУДЕМ ИСПОЛЬЗОВАТЬ ФУНКЦИЮ "ДИСКРЕТНОЙ ЭНТРОПИИ"
$$
F(n)=\sum_{1<k\le n}(\ceil{\log_2 k}+1)=B(n)+n-1
=n\ceil{\log_2 n}-2^{\ceil{\log_2 n}}+n,
\eqno(19)
$$
ГДЕ $B(n)$ ЕСТЬ ФУНКЦИЯ "БИНАРНОЙ ВСТАВКИ" (СМ. ФОРМУЛУ (5.3.1-3)). 
ёОГЛАСНО (5.3.1-33), ФУНКЦИЯ $F(n)$ ЕСТЬ НЕ ЧТО ИНОЕ, КАК МИНИМАЛЬНАЯ 
ДЛИНА ВНЕШНЕГО ПУТИ БИНАРНОГО ДЕРЕВА С $n$~ЛИСТЬЯМИ, И  
$$
n\log_2 n\le F(n)\le n\log_2 n+0.0861n.
\eqno(20)
$$
ЄАК КАК $F (n)$ ВЫПУКЛА И УДОВЛЕТВОРЯЕТ 
УСЛОВИЮ~$F(n)=n+F(\floor{n/2})+F(\ceil{n/2})$, ТО ПО ЛЕММЕ~C
$$
F(n)\le F(k)+F(n-k)+n \rem{ПРИ $0\le k\le n$.}
\eqno(21)
$$
¤ТО СООТНОШЕНИЕ ВЫТЕКАЕТ ТАКЖЕ ИЗ ПРЕДСТАВЛЕНИЯ $F$ В ВИДЕ ДЛИНЫ ВНЕШНЕГО 
ПУТИ; В ДАЛЬНЕЙШЕМ ОНО ОКАЖЕТСЯ РЕШАЮЩИМ ФАКТОМ.

ъАК И В П.~5.4.8, МЫ БУДЕМ ПРЕДПОЛАГАТЬ, ЧТО ЛИФТ ВМЕЩАЕТ $b$~ЧЕЛОВЕК, 
КАЖДЫЙ ЭТАЖ ВМЕЩАЕТ $c$~ЧЕЛОВЕК И ИМЕЕТСЯ $n$~ЭТАЖЕЙ. яУСТЬ $s_{ij}$---ЧИСЛО 
ЛЮДЕЙ, НАХОДЯЩИХСЯ В ДАННЫЙ МОМЕНТ НА ЭТАЖЕ~$i$ И СТРЕМЯЩИХСЯ ПОПАСТЬ НА 
ЭТАЖ~$j$. яО ОПРЕДЕЛЕНИЮ 
\emph{ОЦЕНКА СОВМЕСТНОСТИ} ЛЮБОГО РАСПОЛОЖЕНИЯ ЛЮДЕЙ В ЗДАНИИ 
ЕСТЬ~$\sum_{1\le i,j\le n} F(s_{ij})$.

яРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО $b=c=n=6$ И ЧТО ПЕРВОНАЧАЛЬНО 36~ЧЕЛОВЕК 
СЛЕДУЮЩИМ ОБРАЗОМ РАСПРЕДЕЛЕНЫ МЕЖДУ ЭТАЖАМИ:
{\obeyspaces
$$
\vbox{
\line{\tt\indent \]\]\]\]\]\]}
\line{\tt\indent 123456 123456 123456 123456 123456 123456 \hfill \rm (22)}
}
$$
}
ыИФТ ПУСТ И НАХОДИТСЯ НА ЭТАЖЕ 1; "\]" ОБОЗНАЧАЕТ СВОБОДНОЕ МЕСТО. эА 
КАЖДОМ ЭТАЖЕ НАХОДИТСЯ ЧЕЛОВЕК, СТРЕМЯЩИЙСЯ ПОПАСТЬ НА ПРОИЗВОЛЬНЫЙ ЭТАЖ,
 ПОЭТОМУ ВЕЛИЧИНЫ~$s_{ij}$. РАВНЫ~1 И ОЦЕНКА СОВМЕСТНОСТИ РАВНА~0. хСЛИ 
ТЕПЕРЬ ЛИФТ ОТВЕЗЕТ 6~ЧЕЛОВЕК НА ЭТАЖ~2, ТО МЫ ПОЛУЧИМ РАСПОЛОЖЕНИЕ
{\obeyspaces
$$
\vbox{
\line{\tt\indent        123456}
\line{\tt\indent \]\]\]\]\]\] 123456 123456 123456 123456 123456 \hfill 
\rm (23)}
}
$$
}
И ОЦЕНКА СОВМЕСТНОСТИ СТАНЕТ РАВНА $6F(0)+24F(1)+6F(2)=12$. фОПУСТИМ, 
ЛИФТ ПЕРЕВЕЗЕТ |1|, |1|, |2|, |3|, |3|, |4| НА ЭТАЖ~3:
{\obeyspaces
$$
\vbox{
\line{\tt\indent               112334}
\line{\tt\indent \]\]\]\]\]\] 245566 123456 123456 123456 123456 \hfill 
\rm (24)}
}
$$
}
%%447
юЦЕНКА СОВМЕСТНОСТИ ИЗМЕНИЛАСЬ ДО $4F(2)+2F(3)=18$. ъОГДА КАЖДЫЙ ЧЕЛОВЕК 
БУДЕТ В КОНЦЕ КОНЦОВ ПЕРЕВЕЗЕН К СВОЕМУ МЕСТУ НАЗНАЧЕНИЯ, ОЦЕНКОЙ 
СОВМЕСТНОСТИ БУДЕТ $6F(6)=96$.

ЇЛОЙД ЗАМЕТИЛ, ЧТО ОЦЕНКА СОВМЕСТНОСТИ НИКОГДА НЕ УВЕЛИЧИВАЕТСЯ БОЛЬШЕ, 
ЧЕМ НА $b+c$ ЗА ОДНУ ОСТАНОВКУ, ТАК КАК МНОЖЕСТВО ИЗ $s$~ЛЮДЕЙ С РАВНЫМ 
НАЗНАЧЕНИЕМ, ОБоЕДИНЯЯСЬ С АНАЛОГИЧНЫМ МНОЖЕСТВОМ МОЩНОСТИ~$s'$, 
УВЕЛИЧИВАЕТ ОЦЕНКУ НА $F(s+s')-F(s)-F(s')\le s+s'$. ЄАКИМ ОБРАЗОМ, ИМЕЕМ 
СЛЕДУЮЩИЙ РЕЗУЛЬТАТ.

\proclaim ЄЕОРЕМА~F. яУСТЬ $t$---ОПРЕДЕЛЕННАЯ ВЫШЕ ОЦЕНКА СОВМЕСТНОСТИ 
НАЧАЛЬНОГО РАСПОЛОЖЕНИЯ ЛЮДЕЙ. ыИФТ ДОЛЖЕН СДЕЛАТЬ ПО КРАЙНЕЙ МЕРЕ
$$
\ceil{(nF(c)-t)/(b+c)}
$$
ОСТАНОВОК, ЧТОБЫ ДОСТАВИТЬ ВСЕХ ЛЮДЕЙ К ИХ МЕСТУ НАЗНАЧЕНИЯ.\endmark


ёФОРМУЛИРУЕМ ЭТОТ РЕЗУЛЬТАТ ПРИМЕНИТЕЛЬНО К ДИСКАМ. фОПУСТИМ, ИМЕЕТСЯ 
$N$~ЗАПИСЕЙ ПО $B$ В КАЖДОМ БЛОКЕ, И ПРЕДПОЛОЖИМ, ЧТО ВО ВНУТРЕННЕЙ 
ПАМЯТИ ОДНОВРЕМЕННО ПОМЕЩАЕТСЯ $M$~ЗАПИСЕЙ. яРИ КАЖДОМ ЧТЕНИИ С ДИСКА ОДИН 
БЛОК ПЕРЕНОСИТСЯ В НАМЯТЬ, А ПРИ КАЖДОЙ ЗАПИСИ ОДИН БЛОК ПОМЕЩАЕТСЯ НА 
ДИСК, И $s_{ij}$ ЕСТЬ ЧИСЛО ЗАПИСЕЙ В БЛОКЕ~$i$, ПРИНАДЛЕЖАЩИХ 
БЛОКУ~$j$. хСЛИ $N\ge B^2$, ТО СУЩЕСТВУЕТ НАЧАЛЬНОЕ РАСПОЛОЖЕНИЕ, ДЛЯ 
КОТОРОГО ВСЕ $s_{ij}\le 1$, И, СЛЕДОВАТЕЛЬНО, ДЛЯ ПЕРЕРАЗМЕЩЕНИЯ 
ЗАПИСЕЙ НЕОБХОДИМО ПРОЧИТАТЬ ПО КРАЙНЕЙ МЕРЕ 
$(N/B)F(B)/M\approx (N \log_2 B)/M$~БЛОКОВ. (хСЛИ $B$ ВЕЛИКО, ТО 
МНОЖИТЕЛЬ~$\log_2 B$ ДЕЛАЕТ ЭТУ НИЖНЮЮ ОЦЕНКУ НЕТРИВИАЛЬНОЙ, НО ЕСЛИ $B=1$,
 ТО НИЖНЮЮ ОЦЕНКУ, ОЧЕВИДНО, МОЖНО УЛУЧШИТЬ.)

\excercises
\ex[M22] т ТЕКСТЕ ОБоЯСНЯЕТСЯ МЕТОД, С ПОМОЩЬЮ КОТОРОГО СРЕДНЕЕ 
ВРЕМЯ ОЖИДАНИЯ, ТРЕБУЕМОЕ ДЛЯ ЧТЕНИЯ ДОЛИ~$x$ ДОРОЖКИ, УМЕНЬШАЕТСЯ 
С~${1\over2}$ 
ДО~${1\over2}(1-x^2)$~ОБОРОТОВ. ¤ТО МИНИМАЛЬНО ВОЗМОЖНОЕ ВРЕМЯ, КОГДА 
ИМЕЕТСЯ ОДИН ДЕРЖАТЕЛЬ ГОЛОВОК. ъАКОВО СООТВЕТСТВУЮЩЕЕ МИНИМАЛЬНОЕ ВРЕМЯ 
ОЖИДАНИЯ, ЕСЛИ ИМЕЮТСЯ \emph{ДВА} ДЕРЖАТЕЛЯ ГОЛОВОК, РАЗНЕСЕННЫЕ НА 
$180^\circ$ (В ПРЕДПОЛОЖЕНИИ, ЧТО В ЛЮБОЙ МОМЕНТ ДАННЫЕ МОЖЕТ ПЕРЕДАВАТЬ 
ТОЛЬКО ОДИН ИЗ ДЕРЖАТЕЛЕЙ)?

\ex[M30] (¤.~у.~ъОНХЕЙМ.) ЎЕЛЬ ЭТОЙ ЗАДАЧИ---ИССЛЕДОВАТЬ, НА 
КАКОЕ РАССТОЯНИЕ ДОЛЖЕН ПЕРЕМЕСТИТЬСЯ ДЕРЖАТЕЛЬ ГОЛОВОК ВО ВРЕМЯ СЛИЯНИЯ 
ФАЙЛОВ, РАСПОЛОЖЕННЫХ "ОРТОГОНАЛЬНО" К ЦИЛИНДРАМ фОПУСТИМ, ИМЕЕТСЯ 
$P$~ФАЙЛОВ, КАЖДЫЙ ИЗ КОТОРЫХ СОДЕРЖИТ $L$~БЛОКОВ ЗАПИСЕЙ, И ПРЕДПОЛОЖИМ,
ЧТО ПЕРВЫЙ БЛОК КАЖДОГО ФАЙЛА НАХОДИТСЯ НА ЦИЛИНДРЕ~1, ВТОРОЙ---НА 
ЦИЛИНДРЕ~2 И Т~Д фВИЖЕНИЕМ ДЕРЖАТЕЛЯ ГОЛОВОК ВО ВРЕМЯ СЛИЯНИЯ УПРАВЛЯЕТ 
ОТНОСИТЕЛЬНЫЙ ПОРЯДОК ПОСЛЕДНИХ КЛЮЧЕЙ КАЖДОГО БЛОКА; СЛЕДОВАТЕЛЬНО, 
МОЖНО ИЗОБРАЗИТЬ СИТУАЦИЮ СЛЕДУЮЩИМ СПОСОБОМ, УДОБНЫМ ДЛЯ МАТЕМАТИЧЕСКОЙ
%%448
ИНТЕРПРЕТАЦИИ. ЁАССМОТРИМ МНОЖЕСТВО ИЗ $PL$ УПОРЯДОЧЕННЫХ ПАР
$$
\matrix{
(a_{11},1) & (a_{21},1) & \ldots & (a_{P1},1) \cr
(a_{12},2) & (a_{22},2) & \ldots & (a_{P2},2) \cr
\vdots & \vdots & & \vdots \cr
(a_{1L},L) & (a_{2L},L) & \ldots & (a_{PL},L) \cr
}
$$
ГДЕ МНОЖЕСТВО $\{\, a_{ij} \mid 1\le i\le P, 1\le j\le L\,\}$ 
СООТВЕТСТВУЕТ МНОЖЕСТВУ ЧИСЕЛ $\{\,1, 2, \ldots, PL\,\}$ В НЕКОТОРОМ 
ПОРЯДКЕ И $a_{ij}<a_{i,j+1}$ ПРИ $1\le j<L$ (СТРОКИ ПРЕДСТАВЛЯЮТ ЦИЛИНДРЫ, 
СТОЛБЦЫ---ИСХОДНЫЕ ФАЙЛЫ). юТСОРТИРУЕМ ПАРЫ ПО ИХ ПЕРВЫМ КОМПОНЕНТАМ, И 
ПУСТЬ ПОЛУЧИВШЕЙСЯ ПОСЛЕДОВАТЕЛЬНОСТЬЮ БУДЕТ $(1, j_1)$ $(2, j_2)$ \dots{} 
$(PL, j_{PL})$. яОКАЖИТЕ, ЧТО ЕСЛИ ВСЕ $(PL)!/L!^P$ ВОЗМОЖЛЫХ 
НАБОРОВ~$a_{ij}$ РАВНОВЕРОЯТНЫ, ТО СРЕДНЕЕ ЗНАЧЕНИЕ
$$
\abs{j_2-j_1}+\abs{j_3-j_2}+\cdots+\abs{j_{PL}-j_{PL-1}}
$$
РАВНО
$$
(L-1)\left(1+(P-1)2^{2L-2}/\perm{2L}{L}\right).
$$
[\emph{єКАЗАНИЕ:} СМ. УПР. 5.2.1-14 ] чАМЕТИМ, ЧТО ПРИ  $L\to\infty$ ЭТО 
ЗНАЧЕНИЕ АСИМПТОТИЧЕСКИ РАВНО ${1\over4}(P-1)L\sqrt{\pi L}$.

\ex[ь15] яРЕДПОЛОЖИМ, ЧТО ОГРАНИЧЕННЫЙ РАЗМЕР ВНУТРЕННЕЙ ПАМЯТИ ДЕЛАЕТ 
НЕЖЕЛАТЕЛЬНЫМ $10\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ. ъАК МОЖНО ИЗМЕНИТЬ 
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ (3), (4), (5), ЧТОБЫ $A_1(n)$ СТАЛО МИНИМАЛЬНЫМ 
ЗНАЧЕНИЕМ~$\alpha D(\cJ)+\beta E(\cJ)$ СРЕДИ ВСЕХ ДЕРЕВЬЕВ~$\cJ$ С 
$n$~ЛИСТЬЯМИ, НЕ ИМЕЮЩИХ УЗЛОВ СТЕПЕНИ, БОЛЬШЕЙ ЧЕМ~9?

\rex[ь21] (a) тЫВЕДИТЕ ФОРМУЛУ, АНАЛОГИЧНУЮ (2), ДЛЯ ВРЕМЕНИ ВЫПОЛНЕНИЯ 
$P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ $L$~ЛИТЕР, ЕСЛИ ИСПОЛЬЗУЕТСЯ ВИДОИЗМЕНЕННАЯ 
ФОРМА КВАДРАТИЧНОГО РАСПРЕДЕЛЕНИЯ БУФЕРОВ%
\note{1}{ёМ. ТАКЖЕ ФОРМУЛУ (9).---{\sl яРИМ. РЕД.\/}}: ВСЕ $P$~БУФЕРОВ ВВОДА 
ДОЛЖНЫ ИМЕТЬ РАВНЫЕ ДЛИНЫ, А РАЗМЕР БУФЕРА ВЫВОДА СЛЕДУЕТ ВЫБРАТЬ ТАК, 
ЧТОБЫ МИНИМИЗИРОВАТЬ ВРЕМЯ ПОИСКА.

(b) яОКАЖИТЕ, ЧТО ПОСТРОЕНИЕ В ТЕОРЕМЕ~K МОЖНО ИЗМЕНИТЬ ТАК, ЧТО 
ПОЛУЧИТСЯ СХЕМА СЛИЯНИЯ, КОТОРАЯ БУДЕТ ОПТИМАЛЬНОЙ В СМЫСЛЕ ВАШЕЙ 
ФОРМУЛЫ ИЗ ЧАСТИ~(a).

\ex[ь20] хСЛИ ИСПОЛЬЗУЮТСЯ ДВА ДИСКА, ПРИЧЕМ ЧТЕНИЕ С ОДНОГО СОВМЕЩАЕТСЯ 
С ЗАПИСЬЮ НА ДРУГОЙ, ТО МЫ НЕ МОЖЕМ ПРИМЕНЯТЬ СХЕМУ СЛИЯНИЯ, ПОДОБНУЮ 
ПРЕДСТАВЛЕННОЙ НА РИС.~93, ТАК КАК НЕКОТОРЫЕ ЛИСТЬЯ НАХОДЯТСЯ НА ЧЕТНЫХ 
УРОВНЯХ, А ДРУГИЕ НА НЕЧЕТНЫХ. яОКАЖИТЕ, КАК ИЗМЕНИТЬ ПОСТРОЕНИЕ В 
ТЕОРЕМЕ~K, ЧТОБЫ ПОЛУЧАЛИСЬ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ С УЧЕТОМ ОГРАНИЧЕНИЯ, 
ЧТО ВСЕ ЛИСТЬЯ НАХОДЯТСЯ НА ЧЕТНЫХ УРОВНЯХ ИЛИ ВСЕ НА НЕЧЕТНЫХ.

\rex[22] эАЙДИТЕ ДЕРЕВО, ОПТИМАЛЬНОЕ В СМЫСЛЕ УПР.~6, ЕСЛИ~$n=23$ 
И~$\alpha=\beta=1$. (тОЗМОЖНО, У ВАС ПОЯВИТСЯ ЖЕЛАНИЕ ПРИБЕГНУТЬ К ПОМОЩИ ¤ть.)

\rex[ь24] хСЛИ ДЛИНЫ НАЧАЛЬНЫХ ОТРЕЗКОВ НЕ РАВНЫ, ТО НАИЛУЧШАЯ 
СХЕМА СЛИЯНИЯ (В СМЫСЛЕ ТЕОРЕМЫ~H) МИНИМИЗИРУЕТ $\alpha D(\cJ)+\beta 
E(\cJ)$, ГДЕ $D(\cJ)$ И~$E(\cJ)$ ТЕПЕРЬ ПРЕДСТАВЛЯЮТ СОБОЙ ВЗВЕШЕННЫЕ 
ДЛИНЫ ПУТЕЙ: КАЖДОМУ ЛИСТУ ДЕРЕВА ПРИПИСЫВАЮТСЯ ВЕСА $w_1$,~\dots, $w_n$ 
(СООТВЕТСТВУЮЩИЕ ДЛИНАМ НАЧАЛЬНЫХ ОТРЕЗКОВ), А СУММЫ СТЕПЕНЕЙ И ДЛИНЫ 
ПУТЕЙ УМНОЖАЮТСЯ НА СООТВЕТСТВУЮЩИЕ ВЕСА. эАПРИМЕР, ЕСЛИ $\cJ$---ДЕРЕВО, 
ПРЕДСТАВЛЕННОЕ НА РИС.~92, ТО 
ПОЛУЧИМ $D(\cJ)=6w_1+6w_2+7w_3+9w_4+9w_5+7w_6+4w_7+4w_8$, 
$E (\cJ)=2w_1+2w_2+2w_3+3w_4+3w_5+2w_6+w_7+w_8$.

фОКАЖИТЕ, ЧТО ПРИ НЕКОТОРОМ $k$ ВСЕГДА СУЩЕСТВУЕТ ОПТИМАЛЬНАЯ СХЕМА, В 
КОТОРОЙ ПЕРВЫМИ СЛИВАЮТСЯ $k$ \emph{САМЫХ КОРОТКИХ ОТРЕЗКОВ}.

%%449

\ex[49] ёУЩЕСТВУЕТ, ЛИ АЛГОРИТМ, КОТОРЫЙ ПРИ ЗАДАННЫХ $\alpha$, $\beta$ И 
ВЕСАХ~$w_1$,~\dots, $w_n$ НАХОДИТ ОПТИМАЛЬНЫЕ В СМЫСЛЕ УПР.~7 ДЕРЕВЬЯ, 
ЗАТРАЧИВАЯ ТОЛЬКО $O(n^c)$~ШАГОВ ПРИ НЕКОТОРОМ~$c$?

\ex[M49] (°ЛЮМБЕРГЕР И тИЙЕМАН.) тЕРНО ЛИ, ЧТО ДЛЯ ВСЕХ $n$, $\alpha$ И~$\beta$
СУЩЕСТВУЮТ ОПТИМАЛЬНЫЕ В СМЫСЛЕ ТЕОРЕМЫ~H ДЕРЕВЬЯ С $n$~ЛИСТЬЯМИ, У 
КОТОРЫХ ВСЕ ЛИСТЬЯ НАХОДЯТСЯ САМОЕ БОЛЬШЕЕ НА ДВУХ СОСЕДНИХ УРОВНЯХ? 
хСЛИ $\alpha$ И~$\beta$ ФИКСИРОВАНЫ, СУЩЕСТВУЕТ ЛИ ЧИСЛО $m$, ТАКОЕ, ЧТО 
ДЛЯ ВСЕХ ДОСТАТОЧНО БОЛЬШИХ $n$ ИМЕЕТ МЕСТО $A_1(n)=\alpha mn+\beta 
n+A_m(n)$? (юБА ЭТИ ПРЕДПОЛОЖЕНИЯ БЫЛИ ПРОВЕРЕНЫ В СЛУЧАЕ~$\alpha/\beta\ge 4$.)

\ex[ть49] ъАКОВО АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ $A_1(n)$ ПРИ $n\to\infty$ 
ПРИ ЗАДАННЫХ $\alpha$ И~$\beta$?

\ex[ь29] т ОБОЗНАЧЕНИЯХ (11) И~(16) ДОКАЖИТЕ, ЧТО $f_m(n) + mn\ge 
f(n)$ ПРИ ВСЕХ $m$, $n\ge 2$, И ОПРЕДЕЛИТЕ ВСЕ ТИП, ПРИ КОТОРЫХ ИМЕЕТ 
МЕСТО РАВЕНСТВО.

\ex[25] фОКАЖИТЕ, ЧТО ПРИ ВСЕХ $n>0$ СУЩЕСТВУЕТ ДЕРЕВО С $n$~ЛИСТЬЯМИ И 
МИНИМАЛЬНОЙ ДЛИНОЙ СТЕПЕННОГО ПУТИ (11), ВСЕ ЛИСТЬЯ КОТОРОГО РАСПОЛОЖЕНЫ 
НА ОДНОМ УРОВНЕ.

\ex[M24] яОКАЖИТЕ, ЧТО ПРИ $2\le n \le d(\alpha,\beta)$ ЕДИНСТВЕННОЙ 
НАИЛУЧШЕЙ СХЕМОЙ СЛИЯНИЯ В СМЫСЛЕ ТЕОРЕМЫ~H ЯВЛЯЕТСЯ $n\hbox{-ПУТЕВОЕ}$ 
СЛИЯНИЕ. 
(ёР. С ФОРМУЛОЙ (17).)

\ex[40] яРИ ИСПОЛЬЗОВАНИИ КВАДРАТИЧНОГО МЕТОДА РАСПРЕДЕЛЕНИЯ БУФЕРОВ ВРЕМЯ 
ПОИСКА ДЛЯ -СХЕМЫ СЛИЯНИЯ НА РИС.~92 БУДЕТ ПРОПОРЦИОНАЛЬНО
$(\sqrt{2}+\sqrt{4}+\sqrt{1}+\sqrt{1}+\sqrt{8})^2
+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2+\sqrt{1}+\sqrt{2}
+(\sqrt{1}+\sqrt{4})^2+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2$; 
ЭТО ЗНАЧЕНИЕ ПРЕДСТАВЛЯЕТ СОБОЙ СУММУ
ВЕЛИЧИН $(\sqrt{n_1}+\cdots+\sqrt{n_m}+\sqrt{n_1+\cdots+n_m})^2$ ПО ВСЕМ 
ВНУТРЕННИМ УЗЛАМ, ГДЕ ПОДДЕРЕВЬЯ ЭТИХ УЗЛОВ ИМЕЮТ 
$(n_1, \ldots, n_m)$~ЛИСТЬЕВ. 
эАПИШИТЕ ПРОГРАММУ ДЛЯ ¤ть, КОТОРАЯ ПОРОЖДАЕТ ДЕРЕВЬЯ С 
МИНИМАЛЬНЫМ ВРЕМЕНЕМ ПОИСКА, ИМЕЮЩИЕ $1$, $2$, $3$, \dots{} ЛИСТЬЕВ, 
ИСПОЛЬЗУЯ ДЛЯ ОЦЕНКИ ВРЕМЕНИ ПОИСКА ЭТУ ФОРМУЛУ.

\ex[M22] яОКАЖИТЕ, ЧТО МОЖНО НЕСКОЛЬКО УСИЛИТЬ ТЕОРЕМУ~F, ЕСЛИ 
ЛИФТ ПЕРВОНАЧАЛЬНО ПУСТ И ЕСЛИ $nF(c)\ne t$: В ЭТОМ СЛУЧАЕ НЕОБХОДИМО НЕ 
МЕНЕЕ $\ceil{(nF(c)+b-t)/(b+c)}$~ОСТАНОВОК.

\ex[23] (Ё.~є.~ЇЛОЙД.) эАЙДИТЕ ГРАФИК РАБОТЫ ЛИФТА, ПЕРЕВОЗЯЩИЙ ВСЕХ ЛЮДЕЙ 
ИЗ~(22) К ИХ МЕСТАМ НАЗНАЧЕНИЯ ЗА~12 ИЛИ МЕНЬШЕЕ ЧИСЛО ОСТАНОВОК. (т~(23) 
ПОКАЗАНО ПОЛОЖЕНИЕ ПОСЛЕ ОДНОЙ, А НЕ ПОСЛЕ ДВУХ ОСТАНОВОК.)

\ex[25] (с.~Є.~сЕННЕТ И р.~ў.~ьАК-ъЕЛЛАР, 1971.) ЁАССМОТРИМ СЛЕДУЮЩИЙ 
МЕТОД С СОРТИРОВКОЙ КЛЮЧЕЙ, ПРОДЕМОНСТРИРОВАННЫЙ НА ПРИМЕРЕ ФАЙЛА С 10 КЛЮЧАМИ:
\medskip
\item{a)} шСХОДНЫЙ ФАЙЛ: $(50, I_0)$ $(08, I_1)$ $(51, I_2)$ $(06, I_3)$ $(90, I_4)$ $(17, I_5)$ $(89, I_6)$ $(27, I_7)$ $(65, I_8)$ $(42, I_9)$.

\item{b)} ЇАЙЛ КЛЮЧЕЙ: $(50, 0)$ $(08, 1)$ $(51, 2)$ $(06, 3)$ $(90, 4)$ $(17, 5)$ $(89, 6)$ $(27, 7)$ $(65, 8)$ $(42, 9)$.

\item{c)} юТСОРТИРОВАННЫЙ (b): $(06, 3)$ $(08, 1)$ $(17, 5)$ $(27, 7)$ $(42, 9)$ $(50,0)$ $(51,2)$ $(65, 8)$ $(89, 6)$ $(90, 4)$.

\item{d)} яРИСВАИВАНИЕ НОМЕРОВ ЯЩИКОВ: $(3, 3)$ $(3, 9)$ $(2, 1)$ $(2, 5)$ $(2, 7)$ $(2, 8)$ $(1, 0)$ $(1, 2)$ $(1, 4)$ $(1, 6)$.

\item{e)} юТСОРТИРОВАННЫЙ (d): $(1, 0)$ $(2, 1)$ $(1, 2)$ $(3, 3)$ $(1, 4)$ $(2, 5)$ $(1, 6)$ $(2, 7)$ $(2, 8)$ $(3, 9)$.

\item{f)} (a), РАСПРЕДЕЛЕННЫЙ ПО ЯЩИКАМ С ИСПОЛЬЗОВАНИЕМ (e):
\itemitem{▀ЩИК 1:} $(50, I_0)$ $(51, I_2)$ $(90, I_4)$ $(89, I_6)$.
\itemitem{▀ЩИК 2:} $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(65, I_8)$.
\itemitem{▀ЩИК 3:} $(06, I_3)$ $(42, I_9)$.
\item{g)} ЁЕЗУЛЬТАТ ВЫБОРА С ЗАМЕЩЕНИЕМ (СНАЧАЛА ЧИТАЕТСЯ ЯЩИК~3, 
ЗАТЕМ ЯЩИК~2, ЗАТЕМ ЯЩИК~1): $(06, I_3)$ $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(42, I_9)$ $(50, I_0)$ $(51, I_2)$ $(65, I_8)$ $(89, I_6)$ $(90, I_4)$.
\medskip
\noindent эОМЕРА ЯЩИКОВ НА ШАГЕ~(d) ПРИСВАИВАЮТСЯ ПУТЕМ ПРИМЕНЕНИЯ К~(С) 
\emph{ВЫБОРА С ЗАМЕЩЕНИЕМ СПРАВА НАЛЕВО В УБЫВАЮЩЕМ} ПОРЯДКЕ ПО ВТОРОЙ КОМПОНЕНТЕ.
%%450
эОМЕР ЯЩИКА---ЭТО НОМЕР ОТРЕЗКА. т ПРИВЕДЕННОМ ПРИМЕРЕ ИСПОЛЬЗУЕТСЯ ВЫБОР С 
ЗАМЕЩЕНИЕМ ТОЛЬКО С ДВУМЯ ЭЛЕМЕНТАМИ В ДЕРЕВЕ; ДЛЯ ВЫБОРА С ЗАМЕЩЕНИЕМ 
В~(d) И~(g) ДОЛЖЕН ИСПОЛЬЗОВАТЬСЯ ОДИНАКОВЫЙ РАЗМЕР ДЕРЕВА ВЫБОРА. чАМЕТИМ,
 ЧТО СОДЕРЖИМОЕ ЯЩИКОВ НЕ ОБЯЗАТЕЛЬНО УПОРЯДОЧЕНО.

фОКАЖИТЕ, ЧТО ЭТОТ МЕТОД БУДЕТ СОРТИРОВАТЬ, Т. Е. ЧТО ВЫБОР С ЗАМЕЩЕНИЕМ 
В (g) ОБРАЗУЕТ ЛИШЬ ОДИН ОТРЕЗОК. (¤ТОТ МЕТОД УМЕНЬШАЕТ ЧИСЛО ЯЩИКОВ, 
ТРЕБУЕМОЕ ОБЫЧНОЙ СОРТИРОВКОЙ КЛЮЧЕЙ ПОСРЕДСТВОМ РАСПРЕДЕЛЕНИЯ, ОСОБЕННО 
ЕСЛИ ИСХОДНЫЕ ДАННЫЕ УЖЕ В СИЛЬНОЙ СТЕПЕНИ УПОРЯДОЧЕНЫ.)

\rex[25] эЕКОТОРЫЕ СИСТЕМЫ ПРЕДОСТАВЛЯЮТ ПРОГРАММИСТАМ 
\emph{ВИРТУАЛЬНУЮ ПАМЯТЬ:} МОЖНО ПИСАТЬ ПРОГРАММЫ, ИСХОДЯ ИЗ ПРЕДПОЛОЖЕНИЯ,
 ЧТО ИМЕЕТСЯ ОЧЕНЬ БОЛЬШАЯ ВНУТРЕННЯЯ ПАМЯТЬ, СПОСОБНАЯ ВМЕСТИТЬ ВСЕ 
ДАННЫЕ. ¤ТА ПАМЯТЬ РАЗДЕЛЕНА НА СТРАНИЦЫ, И ЛИШЬ НЕМНОГИЕ ИЗ НИХ 
ДЕЙСТВИТЕЛЬНО НАХОДЯТСЯ ВО ВНУТРЕННЕЙ ПАМЯТИ В ЛЮБОЙ МОМЕНТ ВРЕМЕНИ, 
ОСТАЛЬНЫЕ ЖЕ ХРАНЯТСЯ НА ДИСКАХ ИЛИ БАРАБАНАХ. яРОГРАММИСТУ НЕ НУЖНО 
ВНИКАТЬ ВО ВСЕ ЭТИ ПОДРОБНОСТИ, ТАК КАК СИСТЕМА САМА ОБО ВСЕМ ЗАБОТИТСЯ: 
НОВЫЕ СТРАНИЦЫ АВТОМАТИЧЕСКИ ВЫЗЫВАЮТСЯ В ПАМЯТЬ, КОГДА ОНИ НУЖНЫ.

ьОЖЕТ ПОКАЗАТЬСЯ, ЧТО ПОЯВЛЕНИЕ ВИРТУАЛЬНОЙ ПАМЯТИ ПРИВОДИТ К ОТМИРАНИЮ 
МЕТОДОВ ВНЕШНЕЙ СОРТИРОВКИ, ТАК КАК ЭТА РАБОТА МОЖЕТ БЫТЬ ВЫПОЛНЕНА 
ПРОСТО С ПОМОЩЬЮ МЕТОДОВ, РАЗРАБОТАННЫХ ДЛЯ ВНУТРЕННЕЙ 
СОРТИРОВКИ. ЁАЗБЕРИТЕ ЭТУ СИТУАЦИЮ. яОЧЕМУ СПЕЦИАЛЬНО РАЗРАБОТАННЫЙ МЕТОД 
ВНЕШНЕЙ СОРТИРОВКИ МОЖЕТ ОКАЗАТЬСЯ ЛУЧШЕ ПРИМЕНЕНИЯ ОБЩЕЙ ТЕХНИКИ 
ПОДКАЧКИ СТРАНИЦ К МЕТОДУ ВНУТРЕННЕЙ СОРТИРОВКИ?


\subchap{Ёхч■ьх. шёЄюЁш▀ ш сшсышюуЁрЇш▀} % 5.5
ЄЕПЕРЬ, КОГДА МЫ ПОЧТИ ДОСТИГЛИ КОНЦА ЭТОЙ ОЧЕНЬ ДЛИННОЙ ГЛАВЫ, СТОИТ 
"ОТСОРТИРОВАТЬ" НАИБОЛЕЕ ВАЖНЫЕ ФАКТЫ ИЗ ЧИСЛА ИЗУЧЕННЫХ.

рЛГОРИТМ СОРТИРОВКИ---ЭТО ПРОЦЕДУРА, КОТОРАЯ РЕОРГАНИЗУЕТ ФАЙЛ ЗАПИСЕЙ ТАКИМ 
ОБРАЗОМ, ЧТОБЫ КЛЮЧИ ОКАЗАЛИСЬ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. сЛАГОДАРЯ ТАКОМУ 
УПОРЯДОЧЕННОМУ РАСПОЛОЖЕНИЮ ГРУППИРУЮТСЯ ЗАПИСИ С РАВНЫМИ КЛЮЧАМИ, 
СТАНОВИТСЯ ВОЗМОЖНОЙ ЭФФЕКТИВНАЯ ОБРАБОТКА МНОГИХ ФАЙЛОВ, 
ОТСОРТИРОВАННЫХ ПО ОДНОМУ КЛЮЧУ, СОЗДАЕТСЯ ОСНОВА ДЛЯ 
ЭФФЕКТИВНЫХ АЛГОРИТМОВ ВЫБОРКИ И БОЛЕЕ УБЕДИТЕЛЬНО ВЫГЛЯДЯТ ДОКУМЕНТЫ,
 ПОДГОТОВЛЕННЫЕ С ПОМОЩЬЮ ¤ть.

\emph{тНУТРЕННЯЯ СОРТИРОВКА} ИСПОЛЬЗУЕТСЯ В ТЕХ СЛУЧАЯХ, КОГДА ВСЕ ЗАПИСИ 
ПОМЕЩАЮТСЯ В БЫСТРОЙ ВНУТРЕННЕЙ ПАМЯТИ МАШИНЫ. ьЫ ИЗУЧИЛИ С РАЗНОЙ 
СТЕПЕНЬЮ ДЕТАЛИЗАЦИИ БОЛЕЕ ДВУХ ДЕСЯТКОВ АЛГОРИТМОВ ВНУТРЕННЕЙ СОРТИРОВКИ, 
НО НАМ, НАВЕРНОЕ, БЫЛО БЫ КУДА СПОКОЙНЕЕ, ЕСЛИ БЫ МЫ НЕ ЗНАЛИ ТАК МНОГО 
РАЗЛИЧНЫХ ПОДХОДОВ К ЭТОЙ ЗАДАЧЕ! шЗУЧЕНИЕ ВСЕХ ЭТИХ МЕТОДОВ БЫЛО ПРИЯТНЫМ 
ВРЕМЯПРОВОЖДЕНИЕМ. эО ТЕПЕРЬ ПЕРЕД НАМИ БЕЗРАДОСТНАЯ 
ПЕРСПЕКТИВА---ПРЕДСТОИТ НА ДЕЛЕ РЕШИТЬ, КАКОЙ МЕТОД СЛЕДУЕТ ИСПОЛЬЗОВАТЬ В 
ТОЙ ИЛИ ИНОЙ КОНКРЕТНОЙ СИТУАЦИИ.

сЫЛО БЫ ПРЕКРАСНО, ЕСЛИ БЫ ТОЛЬКО ОДИН ИЛИ ДВА МЕТОДА СОРТИРОВКИ 
ПРЕВОСХОДИЛИ ВСЕ ОСТАЛЬНЫЕ БЕЗОТНОСИТЕЛЬНО К ПРИЛОЖЕНИЮ ИЛИ ИСПОЛЬЗУЕМОЙ 
МАШИНЕ. эА САМОМ ЖЕ ДЕЛЕ КАЖДЫЙ МЕТОД ИМЕЕТ СВОИ СОБСТВЕННЫЕ, ОДНОМУ ЕМУ 
ПРИСУЩИЕ ДОСТОИНСТВА. эАПРИМЕР, МЕТОД ПУЗЫРЬКА (АЛГОРИТМ~5.2.2т) НЕ ИМЕЕТ 
ЯРКО ВЫРАЖЕННЫХ ПРЕИМУЩЕСТВ, ТАК КАК ВСЕГДА МОЖНО НАЙТИ ЛУЧШИЙ СПОСОБ 
СДЕЛАТЬ ТО, ЧТО ОН ДЕЛАЕТ; НО ДАЖЕ ЭТОТ МЕТОД ПОСЛЕ СООТВЕТСТВУЮЩЕГО 
ОБОБЩЕНИЯ ОКАЗЫВАЕТСЯ ПОЛЕЗНЫМ ДЛЯ СОРТИРОВКИ С ДВУМЯ ЛЕНТАМИ (СМ. 
П.~5.4.8). шТАК, ПРИХОДИМ К ЗАКЛЮЧЕНИЮ, ЧТО ПОЧТИ ВСЕ АЛГОРИТМЫ 
ЗАСЛУЖИВАЮТ ТОГО, ЧТОБЫ О НИХ ПОМНИЛИ, ТАК КАК СУЩЕСТВУЮТ ПРИЛОЖЕНИЯ, В 
КОТОРЫХ ОНИ ОКАЗЫВАЮТСЯ ВЕСЬМА ХОРОШИМИ.

т СЛЕДУЮЩЕМ КРАТКОМ ОБЗОРЕ ОСВЕЩАЮТСЯ ОСНОВНЫЕ АСПЕКТЫ НАИБОЛЕЕ ВАЖНЫХ 
АЛГОРИТМОВ ВНУТРЕННЕЙ СОРТИРОВКИ, С КОТОРЫМИ МЫ ВСТРЕЧАЛИСЬ. (ъАК ОБЫЧНО,
 $N$ ОЗНАЧАЕТ ЧИСЛО ЗАПИСЕЙ В ФАЙЛЕ.)

%%452

1. {\sl ЁАСПРЕДЕЛЯЮЩИЙ ПОДСЧЕТ.\/} рЛГОРИТМ~5.2D ОЧЕНЬ ПОЛЕЗЕН, ЕСЛИ 
ДИАПАЗОН КЛЮЧЕЙ НЕВЕЛИК. ьЕТОД УСТОЙЧИВ (НЕ ИЗМЕНЯЕТСЯ ПОРЯДОК ЗАПИСЕЙ С 
РАВНЫМИ КЛЮЧАМИ), НО ТРЕБУЕТСЯ ПАМЯТЬ ДЛЯ СЧЕТЧИКОВ И $2N$~ЗАПИСЕЙ. юДНА 
ИЗ МОДИФИКАЦИЙ, ЭКОНОМЯЩАЯ $N$ ИЗ ЭТИХ ЗАПИСЕЙ ЦЕНОЙ УСТОЙЧИВОСТИ, 
ВСТРЕЧАЕТСЯ В УПР. 5.2-13.

2. {\sl яРОСТЫЕ ВСТАВКИ.\/} рЛГОРИТМ 5.2.1S НАИБОЛЕЕ ПРОСТ 
ДЛЯ ПРОГРАММИРОВАНИЯ, НЕ ТРЕБУЕТ ДОПОЛНИТЕЛЬНОГО ПРОСТРАНСТВА И ВПОЛНЕ 
ЭФФЕКТИВЕН ПРИ МАЛЫХ~$N$ (СКАЖЕМ, ПРИ $N\le 25$). яРИ БОЛЬШИХ~$N$ ОН 
СТАНОВИТСЯ НЕВЫНОСИМО МЕДЛЕННЫМ, ЕСЛИ ТОЛЬКО ИСХОДНЫЕ ДАННЫЕ НЕ ОКАЖУТСЯ 
СРАЗУ ПОЧТИ УПОРЯДОЧЕННЫМИ.

3. {\sl ёОРТИРОВКА С УБЫВАЮЩИМ ШАГОМ.\/} рЛГОРИТМ 5.2.1D (МЕТОД °ЕЛЛА) ТАК 
ЖЕ ДОВОЛЬНО ПРОСТО ПРОГРАММИРУЕТСЯ, ИСПОЛЬЗУЕТ МИНИМАЛЬНЫЙ ОБоЕМ ПАМЯТИ И 
ДОВОЛЬНО ЭФФЕКТИВЕН ПРИ УМЕРЕННО БОЛЬШИХ~$N$ (СКАЖЕМ, ПРИ $N\le 1000$).

4. {\sl тСТАВКИ В СПИСОК.\/} рЛГОРИТМ 5.2.1L ОСНОВАН НА ТОЙ ЖЕ ИДЕЕ, ЧТО И 
ПРОСТЫЕ ВСТАВКИ, И ПОЭТОМУ ГОДИТСЯ ТОЛЬКО ПРИ НЕБОЛЬШИХ~$N$. ъАК И В 
ДРУГИХ МЕТОДАХ СОРТИРОВКИ СПИСКОВ, В НЕМ БЛАГОДАРЯ ОПЕРАЦИЯМ СО ССЫЛКАМИ 
ЭКОНОМИТСЯ СТОИМОСТЬ ПЕРЕМЕЩЕНИЯ ДЛИННЫХ ЗАПИСЕЙ; ЭТО ОСОБЕННО УДОБНО, 
КОГДА ЗАПИСИ ИМЕЮТ ПЕРЕМЕННУЮ ДЛИНУ ИЛИ ЯВЛЯЮТСЯ ЧАСТЬЮ ДРУГИХ СТРУКТУР ДАННЫХ.

5. {\sl ёОРТИРОВКА С ВЫЧИСЛЕНИЕМ АДРЕСА\/} ЭФФЕКТИВНА, ЕСЛИ КЛЮЧИ 
 ПОДЧИНЯЮТСЯ ИЗВЕСТНОМУ (ОБЫЧНО РАВНОМЕРНОМУ) ЗАКОНУ РАСПРЕДЕЛЕНИЯ; 
ВАЖНЕЙШИМИ ВАРИАНТАМИ ЭТОГО ПОДХОДА ЯВЛЯЮТСЯ \emph{ВСТАВКИ В НЕСКОЛЬКО СПИСКОВ}
(АЛГОРИТМ 5.2.1ь) И КОМБИНИРОВАННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА СО 
ВСТАВКАМИ ьАКЛАРЕНА (РАССМОТРЕННАЯ В КОНЦЕ П.~5.2.5). фЛЯ ПОСЛЕДНЕГО 
МЕТОДА ДОСТАТОЧНО ИМЕТЬ $O(\sqrt{N})$ ДОПОЛНИТЕЛЬНЫХ ЯЧЕЕК ПАМЯТИ.

6. {\sl юБМЕННАЯ СОРТИРОВКА СО СЛИЯНИЕМ.\/} рЛГОРИТМ 5.2.2ь (МЕТОД 
сЭТЧЕРА) И РОДСТВЕННЫЙ ЕМУ АЛГОРИТМ \emph{БИТОННОЙ 
СОРТИРОВКИ} (УПР.~5.3.4-10) ПОЛЕЗНЫ, ЕСЛИ МОЖНО ОДНОВРЕМЕННО 
ВЫПОЛНЯТЬ БОЛЬШОЕ ЧИСЛО СРАВНЕНИЙ.

7. {\sl юБМЕННАЯ СОРТИРОВКА С РАЗДЕЛЕНИЕМ\/} (МЕТОД їОАРА, 
ШИРОКО ИЗВЕСТНЫЙ КАК \emph{БЫСТРАЯ СОРТИРОВКА}). рЛГОРИТМ 5.2.2Q, ВЕРОЯТНО,
 САМЫЙ ПОЛЕЗНЫЙ УНИВЕРСАЛЬНЫЙ АЛГОРИТМ ВНУТРЕННЕЙ СОРТИРОВКИ, ПОСКОЛЬКУ 
ОН ТРЕБУЕТ ОЧЕНЬ МАЛО ПАМЯТИ И ОПЕРЕЖАЕТ СВОИХ КОНКУРЕНТОВ ПО СРЕДНЕМУ 
ВРЕМЕНИ ВЫПОЛНЕНИЯ НА БОЛЬШИНСТВЕ ВЫЧИСЛИТЕЛЬНЫХ МАШИН. юДНАКО В 
НАИХУДШЕМ СЛУЧАЕ ОН МОЖЕТ РАБОТАТЬ ОЧЕНЬ МЕДЛЕННО. яОЭТОМУ, ЕСЛИ 
ВЕРОЯТНОСТЬ НЕСЛУЧАЙНЫХ ДАННЫХ ДОСТАТОЧНО ВЕЛИКА, ПРИХОДИТСЯ 
ТЩАТЕЛЬНО ВЫБИРАТЬ РАЗДЕЛЯЮЩИЙ ЭЛЕМЕНТ. хСЛИ ВЫБИРАЕТСЯ МЕДИАНА ИЗ ТРЕХ 
ЭЛЕМЕНТОВ (КАК ПРЕДЛАГАЕТСЯ В УПР. 5.2.2-55), ТО ТАКОЕ
%%453
ПОВЕДЕНИЕ, КАК В НАИХУДШЕМ СЛУЧАЕ, СТАНОВИТСЯ КРАЙНЕ МАЛОВЕРОЯТНЫМ И, 
КРОМЕ ТОГО, НЕСКОЛЬКО УМЕНЬШАЕТСЯ СРЕДНЕЕ ВРЕМЯ РАБОТЫ.

8.~{\sl яРОСТОЙ ВЫБОР.\/} рЛГОРИТМ~5.2.3S ДОВОЛЬНО ПРОСТ И ОСОБЕННО 
ПОДХОДИТ В СЛУЧАЕ, КОГДА ИМЕЕТСЯ СПЕЦИАЛЬНОЕ ОБОРУДОВАНИЕ ДЛЯ БЫСТРОГО 
ПОИСКА НАИМЕНЬШЕГО ЭЛЕМЕНТА В СПИСКЕ.

9.~{\sl яИРАМИДАЛЬНАЯ СОРТИРОВКА.\/} рЛГОРИТМ~5.2.4э ПРИ МИНИМАЛЬНЫХ 
ТРЕБОВАНИЯХ ПАМЯТИ ОБЕСПЕЧИВАЕТ ДОСТАТОЧНО ВЫСОКУЮ СКОРОСТЬ СОРТИРОВКИ; 
КАК СРЕДНЕЕ ВРЕМЯ РАБОТЫ, ТАК И МАКСИМАЛЬНОЕ ВРЕМЯ ПРИМЕРНО ВДВОЕ БОЛЬШЕ 
СРЕДНЕГО ВРЕМЕНИ БЫСТРОЙ СОРТИРОВКИ.

10.~{\sl  ёЛИЯНИЕ СПИСКОВ.\/} рЛГОРИТМ~5.2.4L ОСУЩЕСТВЛЯЕТ СОРТИРОВКУ 
СПИСКОВ, ПРИ КОТОРОЙ, ТАК ЖЕ КАК И ПРИ ПИРАМИДАЛЬНОЙ СОРТИРОВКЕ, 
ОБЕСПЕЧИВАЕТСЯ ВЕСЬМА ВЫСОКАЯ СКОРОСТЬ ДАЖЕ В НАИХУДШЕМ СЛУЧАЕ, КРОМЕ 
ТОГО, ЭТОТ МЕТОД УСТОЙЧИВ ПО ОТНОШЕНИЮ К РАВНЫМ КЛЮЧАМ.

11.~{\sl  яОРАЗРЯДНАЯ СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА\/} 5.2.5R---ЭТО 
НЕ ЧТО ИНОЕ, КАК СОРТИРОВКА СПИСКОВ, КОТОРАЯ ПРИЕМЛЕМА ДЛЯ КЛЮЧЕЙ, ЛИБО 
ОЧЕНЬ КОРОТКИХ, ЛИБО ИМЕЮЩИХ НЕОБЫЧНЫЙ ПОРЯДОК ЛЕКСИКОГРАФИЧЕСКОГО 
СРАВНЕНИЯ. тМЕСТО ССЫЛОК МОЖНО ПРИМЕНИТЬ РАСПРЕДЕЛЯЮЩИЙ ПОДСЧЕТ 
(ПУНКТ~1 НАШЕГО ОБЗОРА); ТАКАЯ ПРОЦЕДУРА ПОТРЕБУЕТ ПРОСТРАНСТВА ДЛЯ 
$2N$~ЗАПИСЕЙ И ДЛЯ ТАБЛИЦЫ, СЧЕТЧИКОВ, НО БЛАГОДАРЯ ПРОСТОТЕ ВНУТРЕННЕГО 
ЦИКЛА ОНА ОСОБЕННО ХОРОША ДЛЯ СВЕРХБЫСТРЫХ ¤ть---"ПОЖИРАТЕЛЬНИЦ ЧИСЕЛ", 
ИМЕЮЩИХ ОПЕРЕЖАЮЩЕЕ УПРАВЛЕНИЕ. (\emph{яРЕДОСТЕРЕЖЕНИЕ.} яОРАЗРЯДНУЮ 
СОРТИРОВКУ НЕ СЛЕДУЕТ ИСПОЛЬЗОВАТЬ ПРИ МАЛЫХ~$N$.)

12.~{\sl  ёОРТИРОВКА ВСТАВКАМИ И СЛИЯНИЕМ\/} (СМ.~П.~5.3.1) 
НАИБОЛЕЕ ПРИЕМЛЕМА ПРИ ОЧЕНЬ МАЛЫХ~$N$ В "ПРЯМОЛИНЕЙНЫХ" 
ПРОГРАММАХ. эАПРИМЕР, ЭТОТ МЕТОД ОКАЗАЛСЯ БЫ ПОДХОДЯЩИМ В ТЕХ 
ПРИЛОЖЕНИЯХ, ГДЕ ТРЕБУЕТСЯ СОРТИРОВАТЬ МНОГО ГРУПП ИЗ ПЯТИ ИЛИ 
ШЕСТИ ЗАПИСЕЙ.

13.  ьОГУТ СУЩЕСТВОВАТЬ И ГИБРИДНЫЕ МЕТОДЫ, ОБоЕДИНЯЮЩИЕ ОДИН ИЛИ БОЛЕЕ ИЗ 
ПРИВЕДЕННЫХ ВЫШЕ МЕТОДОВ. эАПРИМЕР, КОРОТКИЕ ПОДФАЙЛЫ, ВОЗНИКАЮЩИЕ ПРИ 
БЫСТРОЙ СОРТИРОВКЕ, МОЖНО СОРТИРОВАТЬ СЛИЯНИЕМ И ВСТАВКАМИ.

14. ш НАКОНЕЦ, ДЛЯ РЕАЛИЗАЦИИ БЕЗЫМЯННОГО МЕТОДА, ВСТРЕТИВШЕГОСЯ В 
ОТВЕТЕ К УПР.~5.2.1-3, ТРЕБУЕТСЯ, ПО-ВИДИМОМУ, КРАТЧАЙШАЯ ИЗ ВОЗМОЖНЫХ 
ПРОГРАММ СОРТИРОВКИ. эО СРЕДНЕЕ ВРЕМЯ РАБОТЫ ТАКОЙ ПРОГРАММЫ 
ПРОПОРЦИОНАЛЬНО~$N^3$, Т.~Е.~ЭТО САМАЯ МЕДЛЕННАЯ ПРОГРАММА СОРТИРОВКИ В КНИГЕ!

яРОСТРАНСТВЕННЫЕ И ВРЕМЕННЫЕ ХАРАКТЕРИСТИКИ МНОГИХ ИЗ ЭТИХ МЕТОДОВ, 
ЗАПРОГРАММИРОВАННЫХ ДЛЯ \MIX, СВЕДЕНЫ В ТАБЛ.~1.
%%454
\picture{ЄАБЛИЦА 1, СТР. 454}
тАЖНО ИМЕТЬ В ВИДУ, ЧТО ЧИСЛА В ЭТОЙ ТАБЛИЦЕ ЯВЛЯЮТСЯ ЛИШЬ ГРУБЫМИ 
ПОКАЗАТЕЛЯМИ ОТНОСИТЕЛЬНОГО ВРЕМЕНИ СОРТИРОВКИ. юНИ ПРИМЕНИМЫ ТОЛЬКО К 
ОДНОЙ ¤ть, И ПРЕДПОЛОЖЕНИЯ, КАСАЮЩИЕСЯ ИСХОДНЫХ ДАННЫХ, ДАЛЕКО НЕ ДЛЯ ВСЕХ 
ПРОГРАММ АБСОЛЮТНО ПРАВОМЕРНЫ. ёРАВНИТЕЛЬНЫЕ ТАБЛИЦЫ, ПОДОБНЫЕ ЭТОЙ, 
ПРИВОДИЛИСЬ ВО МНОГИХ РАБОТАХ, НО НЕ НАЙДЕТСЯ ТАКИХ ДВУХ АВТОРОВ,
 КОТОРЫЕ ПРИШЛИ БЫ К ОДИНАКОВЫМ ВЫВОДАМ! ЄЕМ НЕ МЕНЕЕ УКАЗАНИЯ О ВРЕМЕНИ 
РАБОТЫ ПОЗВОЛЯЮТ ОЦЕНИТЬ ХОТЯ БЫ ПОРЯДОК СКОРОСТИ, КОТОРУЮ СЛЕДУЕТ ОЖИДАТЬ 
ОТ КАЖДОГО АЛГОРИТМА ПРИ СОРТИРОВКЕ ЗАПИСЕЙ ИЗ ОДНОГО СЛОВА, ТАК КАК 
\MIX---ДОВОЛЬНО ТИПИЧНАЯ МАШИНА.

ёТОЛБЕЦ "ПРОСТРАНСТВО" В ТАБЛ.~1 СОДЕРЖИТ НЕКОТОРУЮ ИНФОРМАЦИЮ О 
КОЛИЧЕСТВЕ ВСПОМОГАТЕЛЬНОЙ ПАМЯТИ, ИСПОЛЬЗУЕМОЙ КАЖДЫМ АЛГОРИТМОМ, В 
ЕДИНИЦАХ ДЛИНЫ ЗАПИСИ. чДЕСЬ БУКВОЙ~$\varepsilon$ ОБОЗНАЧЕНА ДОЛЯ ЗАПИСИ, 
ТРЕБУЕМАЯ ДЛЯ ОДНОГО ПОЛЯ СВЯЗИ; ТАК, НАПРИМЕР, $N(1+\varepsilon)$ 
ОЗНАЧАЕТ, ЧТО МЕТОД ТРЕБУЕТ ПРОСТРАНСТВО ДЛЯ $N$~ЗАПИСЕЙ И $N$~ПОЛЕЙ СВЯЗИ.

т АСИМПТОТИЧЕСКИХ СРЕДНИХ И МАКСИМАЛЬНЫХ ВРЕМЕНАХ, СОДЕРЖАЩИХСЯ В 
ТАБЛ.~1, УЧИТЫВАЮТСЯ ТОЛЬКО ГЛАВНЫЕ ЧЛЕНЫ, ДОМИНИРУЮЩИЕ ПРИ БОЛЬШИХ~$N$ В 
ПРЕДПОЛОЖЕНИИ СЛУЧАЙНЫХ ИСХОДНЫХ ДАННЫХ; $c$~ОБОЗНАЧАЕТ ПРОИЗВОЛЬНУЮ 
КОНСТАНТУ. ¤ТИ ФОРМУЛЫ МОГУТ ИНОГДА ВВЕСТИ В ЗАБЛУЖДЕНИЕ, ПОЭТОМУ 
УКАЗАНО ТАКЖЕ ФАКТИЧЕСКОЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ ДЛЯ ДВУХ КОНКРЕТНЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИСХОДНЫХ ДАННЫХ. ёЛУЧАЙ $N=16$, ОТНОСИТСЯ К 
ШЕСТНАДЦАТИ КЛЮЧАМ, ТАК ЧАСТО ПОЯВЛЯВШИМСЯ В ПРИМЕРАХ \S~5.2, А СЛУЧАЙ 
$N=1000$ ОТНОСИТСЯ К ПОСЛЕДОВАТЕЛЬНОСТИ $K_1$, $K_2$,~\dots, $K_{1000}$, 
ОПРЕДЕЛЕННОЙ ФОРМУЛАМИ
$$
K_0=0; \quad K_{n+1}=(3141592621K_n+2113148651)\bmod 10^{10}.
$$
фЛЯ ПОЛУЧЕНИЯ ХАРАКТЕРИСТИК КАЖДОГО АЛГОРИТМА, ПРЕДСТАВЛЕННОГО В ТАБЛИЦЕ,
 ИСПОЛЬЗОВАЛАСЬ ВПОЛНЕ "ВЫСОКОКАЧЕСТВЕННАЯ" \MIX-ПРОГРАММА, ЧАСТО С УЧЕТОМ 
УСОВЕРШЕНСТВОВАНИЙ, ПРЕДЛОЖЕННЫХ В УПРАЖНЕНИЯХ. ЁАЗМЕР БАЙТА ПРИ 
ВЫПОЛНЕНИИ ЭТИХ ПРОГРАММ ПРИНЯТ РАВНЫМ 100.

фЛЯ \emph{ВНЕШНЕЙ СОРТИРОВКИ} НЕОБХОДИМЫ МЕТОДЫ, ОТЛИЧАЮЩИЕСЯ ОТ МЕТОДОВ 
ВНУТРЕННЕЙ СОРТИРОВКИ, ПОТОМУ ЧТО В ЭТОМ СЛУЧАЕ ПРЕДПОЛАГАЕТСЯ 
ИСПОЛЬЗОВАНИЕ СРАВНИТЕЛЬНО ПРОСТЫХ СТРУКТУР ДАННЫХ И БОЛЬШОЕ ВНИМАНИЕ 
УДЕЛЯЕТСЯ УМЕНЬШЕНИЮ ВРЕМЕНИ ВВОДА/ВЫВОДА. т П.~5.4.6 РАССМАТРИВАЮТСЯ 
ИНТЕРЕСНЫЕ МЕТОДЫ, РАЗВИТЫЕ ДЛЯ ЛЕНТОЧНОЙ СОРТИРОВКИ, А В П.~5.4.9 
ОБСУЖДАЕТСЯ ИСПОЛЬЗОВАНИЕ ДИСКОВ И БАРАБАНОВ.

ъОНЕЧНО, СОРТИРОВКА---НЕ ЕДИНСТВЕННОЕ СОДЕРЖАНИЕ ЭТОЙ ГЛАВЫ. яОПУТНО МЫ 
УЗНАЛИ МНОГО О ТОМ, КАК РАБОТАТЬ СО СТРУКТУРАМИ ДАННЫХ, КАК ОБРАЩАТЬСЯ С 
ВНЕШНЕЙ ПАМЯТЬЮ И КАК АНАЛИЗИРОВАТЬ АЛГОРИТМЫ, И, НАВЕРНОЕ, МЫ УЗНАЛИ 
НЕМНОЖКО И О ТОМ, КАК ОТКРЫВАТЬ НОВЫЕ АЛГОРИТМЫ.
%%456

\section ЁАННИЕ РАЗРАБОТКИ. яОИСК ИСТОЧНИКА СОВРЕМЕННЫХ МЕТОДОВ 
СОРТИРОВКИ ВОЗВРАЩАЕТ НАС В 19-Е~СТОЛЕТИЕ, КОГДА БЫЛИ ИЗОБРЕТЕНЫ ПЕРВЫЕ 
МАШИНЫ ДЛЯ СОРТИРОВКИ. т ёОЕДИНЕННЫХ °ТАТАХ ПЕРЕПИСЬ ВСЕХ ГРАЖДАН 
ПРОВОДИТСЯ КАЖДЫЕ 10~ЛЕТ, И УЖЕ К 1880~Г. ПРОБЛЕМА ОБРАБОТКИ ОГРОМНЫХ ПО 
ОБоЕМУ ДАННЫХ ПЕРЕПИСИ СТАЛА ОЧЕНЬ ОСТРОЙ; И В САМОМ ДЕЛЕ, ЧИСЛО ОДИНОКИХ 
(В ОТЛИЧИЕ ОТ ЧИСЛА СОСТОЯЩИХ В БРАКЕ) В 1880~Г. В ТАБЛИЦАХ ОТСУТСТВУЕТ, ХОТЯ
\picture{ЁИС. 94. ЄАБУЛЯТОР їОЛЛЕРИТА. (ЇОТОГРАФИЯ ЛЮБЕЗНО ПРЕДОСТАВЛЕНА 
АРХИВОМ IBM.)
}
ВСЯ НЕОБХОДИМАЯ, ИНФОРМАЦИЯ БЫЛА СОБРАНА. уЕРМАН їОЛЛЕРИТ, ДВАДЦАТИЛЕТНИЙ 
СЛУЖАЩИЙ сЮРО ПЕРЕПИСИ, ИЗОБРЕЛ ОСТРОУМНЫЙ ЭЛЕКТРИЧЕСКИЙ ТАБУЛЯТОР, 
ОТВЕЧАЮЩИЙ НУЖДАМ СБОРА СТАТИСТИКИ, И ОКОЛО 100 ЕГО МАШИН УСПЕШНО 
ИСПОЛЬЗОВАЛИСЬ ПРИ ОБРАБОТКЕ СПИСКОВ ПЕРЕПИСИ 1890~Г.

эА РИС.~94 ИЗОБРАЖЕН ПЕРВЫЙ АППАРАТ їОЛЛЕРИТА, ПРИВОДИМЫЙ В ДЕЙСТВИЕ ОТ 
АККУМУЛЯТОРНЫХ БАТАРЕЙ. фЛЯ НАС ОСНОВНОЙ ИНТЕРЕС ПРЕДСТАВЛЯЕТ 
"СОРТИРОВАЛЬНЫЙ ЯЩИК" СПРАВА, КОТОРЫЙ ОТКРЫТ С  ЦЕЛЬЮ ПОКАЗАТЬ ПОЛОВИНУ ИЗ 
26 ВНУТРЕННИХ ОТДЕЛЕНИЙ. юПЕРАТОР ВСТАВЛЯЕТ ПЕРФОКАРТУ РАЗМЕРА 
$6{5\over8}\times3{1\over4}$~ДЮЙМОВ В "ПРЕСС" И ОПУСКАЕТ РУКОЯТКУ; ЭТО 
ПРИВОДИТ К ТОМУ, ЧТО ЗАКРЕПЛЕННЫЕ НА ПРУЖИНАХ ШТЫРИ НА ВЕРХНЕЙ ПАНЕЛИ В ТЕХ
%%457
\bye