\input style
%% 118
ПРИБЛИЖЕНИЕМ ПРИ $100\le N\le 60\ 000$ СЛУЖАТ СЛЕДУЮЩИЕ ФОРМУЛЫ:
$$
\displaylines{
\hbox{$1.09N^{1.27}$ ИЛИ $.30N(\ln N)^2-1.35N\ln N$ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ 
ШАГОВ $2^k+1$,\dots, 9, 5, 3, 1;}\hfill\cr
\hbox{$1.22N^{1.26}$ ИЛИ $.29N(\ln N)^2-1.26N\ln N$ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ 
ШАГОВ $2^k-1$, \dots, 15, 7, 3, 1;}\hfill\cr
\hbox{$1.12N^{1.28}$ ИЛИ $.36N(\ln N)^2- 1.73N \ln N$ ДЛЯ 
ПОСЛЕДОВАТЕЛЬНОСТИ ШАГОВ $(2^k\pm 1)/3$, \dots, 11, 5, 3, 1;}\hfill\cr
\hbox{$1.66N^{1.25}$ ИЛИ $.33N(\ln N)^2-1.26N\ln N$ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ 
ШАГОВ $(3^k-1)/2$, \dots, 40, 13, 4, 1.}\hfill\cr
}
$$
эАПРИМЕР, ПРИ $N=20\ 000$ ДЛЯ ВСЕХ ЭТИХ ТИПОВ ШАГОВ 
ПОЛУЧАЕМ СООТВЕТСТВЕННО $B\approx 31\ 000$, $33\ 000$, $35\ 000$, 
$39\ 000$. ЄАБЛ.~7 ДАЕТ
\htable{ЄАБЛИЦА 7}%
{ъОЛИЧЕСТВА ПЕРЕМЕЩЕНИЙ ПО ПРОСМОТРАМ (ПРИМЕРЫ ДЛЯ  $N=20 000$)}%
{\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill&\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill&\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill\cr
h_s & B_s & h_s & B_s & h_s & B_s \cr
\noalign{\hrule}
4095 & 19460 & 4097 & 19550 & 3280 & 25210\cr
2047 & 15115 & 2049 & 14944 & 1093 & 28324\cr
1023 & 15869 & 1025 & 15731 &  364 & 35477\cr
 511 & 18891 &  513 & 18548 &  121 & 47158\cr
 255 & 22306 &  257 & 21827 &   40 & 62110\cr
 127 & 27400 &  129 & 27814 &   13 & 88524\cr
  63 & 35053 &   65 & 33751 &    4 & 74599\cr
  31 & 34677 &   33 & 34303 &    1 & 34666\cr
  15 & 51054 &   17 & 46044\cr
   7 & 40382 &    9 & 35817\cr
   3 & 24044 &    5 & 19961\cr
   1 & 16789 &    3 &  9628\cr
     &       &    1 & 13277\cr
\noalign{\hrule}
}
ТИПИЧНУЮ КАРТИНУ ТОГО, КАК РАСПРЕДЕЛЯЮТСЯ ПЕРЕМЕЩЕНИЯ ПО ПРОСМОТРАМ В ТРЕХ 
ИЗ ЭТИХ ЭКСПЕРИМЕНТОВ. ыЮБОПЫТНО, ЧТО \emph{ОБА} ВИДА ФУНКЦИЙ $\alpha N 
(\ln N)^2+\beta N\ln N$ И $\beta N^\alpha$, КАЖЕТСЯ, ДОВОЛЬНО ХОРОШО 
СОГЛАСУЮТСЯ С НАБЛЮДАЕМЫМИ ДАННЫМИ, ХОТЯ СТЕПЕННАЯ ФУНКЦИЯ БЫЛА 
СУЩЕСТВЕННО ЛУЧШЕ ПРИ МЕНЬШИХ ЗНАЧЕНИЯХ $N$. фАЛЬНЕЙШИЕ ЭКСПЕРИМЕНТЫ БЫЛИ 
ВЫПОЛНЕНЫ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ ШАГОВ $2^k-1$ СО ЗНАЧЕНИЕМ $N$, 
ДОСТИГАЮЩИМ $250\ 000$; СОРОК ПЯТЬ ИСПЫТАНИЙ С $N = 250\ 000$ ДАЛИ 
ЗНАЧЕНИЕ $B\approx 7\ 900\ 000$ ПРИ НАБЛЮДАЕМОМ СТАНДАРТНОМ ОТКЛОНЕНИИ 
$50\ 000$. "эАИБОЛЕЕ ПОДХОДЯЩИМИ" ФОРМУЛАМИ ДЛЯ ДИАПАЗОНА $100 \le N \le 
250\ 000$ ОКАЗАЛИСЬ СООТВЕТСТВЕННО $1.21N^{1.26}$ И~$.39N (\ln N)^2- 2.33 
N \ln N$. ЄАК КАК
%%119
КОЭФФИЦИЕНТЫ В ПРЕДСТАВЛЕНИИ СТЕПЕННОЙ ФУНКЦИЕЙ ОСТАЛИСЬ ПОЧТИ ТАКИМИ ЖЕ, 
В ТО ВРЕМЯ КАК КОЭФФИЦИЕНТЫ В ЛОГАРИФМИЧЕСКОМ ПРЕДСТАВЛЕНИИ ДОВОЛЬНО 
РЕЗКО ИЗМЕНИЛИСЬ, ТО РАЗУМНО ПРЕДПОЛОЖИТЬ, ЧТО ИМЕННО СТЕПЕННАЯ ФУНКЦИЯ 
ОПИСЫВАЕТ ИСТИННОЕ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ МЕТОДА °ЕЛЛА.

¤ТИ ЭМПИРИЧЕСКИЕ ДАННЫЕ НИ КОИМ ОБРАЗОМ НЕ ИСЧЕРПЫВАЮТ ВСЕХ ВОЗМОЖНОСТЕЙ, 
И МЫ НЕ ПОЛУЧИЛИ ОСНОВАНИЙ ДЛЯ РЕШИТЕЛЬНЫХ ЗАКЛЮЧЕНИЙ О ТОМ, КАКИЕ ЖЕ 
ПОСЛЕДОВАТЕЛЬНОСТИ ШАГОВ ЯВЛЯЮТСЯ НАИЛУЧШИМИ ДЛЯ АЛГОРИТМА D. яОСКОЛЬКУ 
ПРИРАЩЕНИЯ ВИДА $(3^k-1)/2$ НЕ УВЕЛИЧИВАЮТ СУЩЕСТВЕННО ЧИСЛА 
ПЕРЕМЕЩЕНИЙ И ПОСКОЛЬКУ ДЛЯ НИХ ТРЕБУЕТСЯ ЛИШЬ ПРИМЕРНО 5/8 ЧИСЛА 
ПРОСМОТРОВ, НЕОБХОДИМЫХ ДЛЯ ШАГОВ ДРУГИХ ТИПОВ, ТО, ОЧЕВИДНО,
 \emph{РАЗУМНО ВЫБИРАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ШАГОВ СЛЕДУЮЩИМ ОБРАЗОМ:}
$$
\hbox{\it яРИНЯТЬ $h_t=1$, $h_{s+1}=3h_s+1$ И ОСТАНОВИТЬСЯ НА $h_t$, КОГДА 
$h_{t+2}\ge N$.}
\eqno (8)
$$

\section тСТАВКИ В СПИСОК. юСТАВИМ ТЕПЕРЬ МЕТОД °ЕЛЛА И РАССМОТРИМ ДРУГИЕ 
ПУТИ УСОВЕРШЕНСТВОВАНИЯ ПРОСТЫХ ВСТАВОК. ёРЕДИ ОБЩИХ СПОСОБОВ УЛУЧШЕНИЯ 
АЛГОРИТМА ОДИН ИЗ САМЫХ ВАЖНЫХ ОСНОВЫВАЕТСЯ НА ТЩАТЕЛЬНОМ АНАЛИЗЕ 
СТРУКТУР ДАННЫХ, ПОСКОЛЬКУ РЕОРГАНИЗАЦИЯ СТРУКТУР ДАННЫХ, ПОЗВОЛЯЮЩАЯ 
ИЗБЕЖАТЬ НЕНУЖНЫХ ОПЕРАЦИЙ, ЧАСТО ДАЕТ СУЩЕСТВЕННЫЙ ЭФФЕКТ. фАЛЬНЕЙШЕЕ 
ОБСУЖДЕНИЕ ЭТОЙ ОБЩЕЙ ИДЕИ МОЖНО НАЙТИ В \S~2.4, В КОТОРОМ 
ИЗУЧАЕТСЯ ДОВОЛЬНО СЛОЖНЫЙ АЛГОРИТМ. яОСМОТРИМ, КАК ОНА ПРИМЕНЯЕТСЯ К 
ТАКОМУ НЕХИТРОМУ АЛГОРИТМУ, КАК ПРОСТЫЕ ВСТАВКИ. ъАКОВА НАИБОЛЕЕ 
ПОДХОДЯЩАЯ СТРУКТУРА ДАННЫХ ДЛЯ АЛГОРИТМА S?

ёОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ СОСТОИТ ИЗ ДВУХ ОСНОВНЫХ ОПЕРАЦИЙ:
\medskip
\item{i)} ПРОСМОТРА УПОРЯДОЧЕННОГО ФАЙЛА ДЛЯ НАХОЖДЕНИЯ НАИБОЛЬШЕГО 
КЛЮЧА, МЕНЬШЕГО ИЛИ РАВНОГО ДАННОМУ КЛЮЧУ;

\item{ii)} ВСТАВКИ НОВОЙ ЗАПИСИ В ОПРЕДЕЛЕННОЕ МЕСТО УПОРЯДОЧЕННОГО ФАЙЛА.
\medskip
\noindent ЇАЙЛ---ЭТО, ОЧЕВИДНО, ЛИНЕЙНЫЙ СПИСОК, И АЛГОРИТМ S ОБРАБАТЫВАЕТ 
ЕГО, ИСПОЛЬЗУЯ ПОСЛЕДОВАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ (П.~2.2.2);
ПОЭТОМУ ДЛЯ ВЫПОЛНЕНИЯ КАЖДОЙ ОПЕРАЦИИ ВСТАВКИ НЕОБХОДИМО ПЕРЕМЕСТИТЬ 
ПРИМЕРНО ПОЛОВИНУ ЗАПИСЕЙ. ё ДРУГОЙ СТОРОНЫ, НАМ ИЗВЕСТНО, ЧТО ДЛЯ ВСТАВОК 
ИДЕАЛЬНО ПОДХОДИТ СВЯЗАННОЕ РАСПРЕДЕЛЕНИЕ (П.~2.2.3), ТАК КАК ПРИ ЭТОМ 
ТРЕБУЕТСЯ ИЗМЕНИТЬ ЛИШЬ НЕСКОЛЬКО СВЯЗЕЙ; ДРУГАЯ ОПЕРАЦИЯ---ПОСЛЕДОВАТЕЛЬНЫЙ 
ПРОСМОТР---ПРИ СВЯЗАННОМ РАСПРЕДЕЛЕНИИ ПОЧТИ ТАК ЖЕ ПРОСТА, КАК И ПРИ 
ПОСЛЕДОВАТЕЛЬНОМ. яОСКОЛЬКУ СПИСКИ ВСЕГДА ПРОСМАТРИВАЮТСЯ В ОДНОМ И ТОМ 
ЖЕ НАПРАВЛЕНИИ, ТО ДОСТАТОЧНО ИМЕТЬ СПИСКИ С ОДНОЙ СВЯЗЬЮ. ЄАКИМ ОБРАЗОМ, 
ПРИХОДИМ К ВЫВОДУ, ЧТО "ПРАВИЛЬНАЯ" СТРУКТУРА ДАННЫХ ДЛЯ МЕТОДА ПРОСТЫХ 
ВСТАВОК---ЛИНЕЙНЫЕ
%% 120
СПИСКИ С ОДНОЙ СВЯЗЬЮ. єДОБНО ТАКЖЕ ИЗМЕНИТЬ АЛГОРИТМ S, 
ЧТОБЫ СПИСОК ПРОСМАТРИВАЛСЯ В  ВОЗРАСТАЮЩЕМ ПОРЯДКЕ.

\alg L.(тСТАВКИ В СПИСОК.) яРЕДПОЛАГАЕТСЯ, ЧТО ЗАПИСИ $R_1$,\dots, $R_N$ 
СОДЕРЖАТ КЛЮЧИ $K_1$, \dots, $K_N$ И~"ПОЛЯ СВЯЗИ" $L_1$, \dots, $L_N$, В 
КОТОРЫХ МОГУТ ХРАНИТЬСЯ ЧИСЛА ОТ~0 ДО~$N$;
ИМЕЕТСЯ ТАКЖЕ ЕЩЕ ОДНО ПОЛЕ СВЯЗИ $L_0$ В НЕКОТОРОЙ ИСКУССТВЕННОЙ ЗАПИСИ 
$R_0$ В НАЧАЛЕ ФАЙЛА. рЛГОРИТМ УСТАНАВЛИВАЕТ ПОЛЯ СВЯЗИ ТАК, ЧТО ЗАПИСИ 
ОКАЗЫВАЮТСЯ СВЯЗАННЫМИ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. ЄАК, ЕСЛИ $p(1) \ldots 
p(N)$---"УСТОЙЧИВАЯ" ПЕРЕСТАНОВКА, ТАКАЯ, ЧТО 
$K_{p(1)}\le \ldots \le K_{p(N)}$, ТО В РЕЗУЛЬТАТЕ ПРИМЕНЕНИЯ АЛГОРИТМА 
ПОЛУЧИМ
$$
L_0=p(1); L_{p(i)}=p(i+1)\ \hbox{ПРИ $1\le i<N$}; L_{p(N)}=0. 
\eqno(9)
$$
\st[ЎИКЛ ПО $j$.] єСТАНОВИТЬ $L_0\asg N$, $L_N\asg0$. ($L_0$ 
СЛУЖИТ "ГОЛОВОЙ" СПИСКА, А 0---ПУСТОЙ СВЯЗЬЮ; СЛЕДОВАТЕЛЬНО, СПИСОК, ПО 
СУЩЕСТВУ, ЦИКЛИЧЕСКИЙ.) тЫПОЛНИТЬ ШАГИ ОТ \stp{2} ДО \stp{5} ПРИ $j=N-1$, 
$N-2$, \dots, $1$ И ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\st[єСТАНОВИТЬ $p$, $q$, $K$.] єСТАНОВИТЬ $p\asg L_0$,  $q\asg0$, 
$K\asg K_j$. (т ПОСЛЕДУЮЩИХ ШАГАХ МЫ ВСТАВИМ ЗАПИСЬ $R_j$ В НУЖНОЕ МЕСТО В 
СВЯЗАННОМ СПИСКЕ ПУТЕМ СРАВНЕНИЯ КЛЮЧА $K$ С ПРЕДЫДУЩИМИ КЛЮЧАМИ В 
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. яЕРЕМЕННЫЕ $p$ И~$q$ СЛУЖАТ УКАЗАТЕЛЯМИ НА ТЕКУЩЕЕ 
МЕСТО В СПИСКЕ, ПРИЧЕМ $p=L_q$, ТАК ЧТО $q$ ВСЕГДА НА ОДИН ШАГ ОТСТАЕТ 
ОТ $p$.)

\st[ёРАВНИТЬ $K$, $K_p$.] хСЛИ $K\le K_p$, ТО ПЕРЕЙТИ К ШАГУ \stp{5}. (ьЫ 
НАШЛИ ИСКОМОЕ ПОЛОЖЕНИЕ ЗАПИСИ $R$ В СПИСКЕ МЕЖДУ $R_q$ И~$R_p$.)

\st[яРОДВИНУТЬ $p$, $q$.] єСТАНОВИТЬ $q\asg p$, $p\asg L_q$. хСЛИ $p>0$,
 ТО ВОЗВРАТИТЬСЯ К ШАГУ \stp{3}. (хСЛИ $p=0$, ТО $K$---НАИБОЛЬШИЙ КЛЮЧ, 
ОБНАРУЖЕННЫЙ ДО СИХ ПОР; СЛЕДОВАТЕЛЬНО, ЗАПИСЬ $R$ ДОЛЖНА ПОПАСТЬ В 
КОНЕЦ СПИСКА, МЕЖДУ $R_q$ И $R_0$.)

\st[тСТАВИТЬ В СПИСОК.] єСТАНОВИТЬ $L_q\asg j$, $L_j\asg p$. 
\algend

\ctable{
\strut\bskip\hfill$#:$\hfill\bskip&&\bskip\hfill#\hfill\bskip\cr
\noalign{\rightline{\it ЄАБЛИЦА 8}}
\noalign{\centerline{\bf яРИМЕР ПРИМЕНЕНИЯ АЛГОРИТМА ВСТАВОК В СПИСОК}}
\noalign{\hrule}
  j&  0&  1&  2&  3&  4&  5&  6&  7&  8&  9& 10& 11& 12& 13& 14& 15& 16\cr
K_i&---&503&087&512&061&908&170&897&275&653&426&154&509&612&677&765&703\cr
L_j& 16&---&---&---&---&---&---&---&---&---&---&---&---&---&---&---&  0\cr
L_j& 16&---&---&---&---&---&---&---&---&---&---&---&---&---&---&  0& 15\cr
L_j& 14&---&---&---&---&---&---&---&---&---&---&---&---&---& 16&  0& 15\cr
\noalign{\hrule}
}
%% 121
\bye