\input style

��� ����� �� �������� �������� ����������� ����� ���� ���������, �� ��� 
��������� ���, ��� ����������, ��� ������ � ���������� ��������� 
��������������� ��� ����������� ���������� ��� � 1946~�., ���� � 
���������� �� ������� ��� ��������� ���� ����� 1960~�.

����������� ����������� ���� ������������� � �������� ������� ���� 
���������� �.~ဉ���� 
[{\sl CACM\/}, {\bf 11} (1968), 491--493]. �� ���� $P+1$ ���� � $S$ 
������; ��������� ����� �� $P$ ���������, ������ �� ������� �������� 
$\lfloor S/P \rfloor$ ��� $\lceil S/P \rceil$ ������, � ���������� ��� 
��������� ���������� � ������� ��������. 呋� $S<2P$, �� ���� ������� 
������ �������� �� ������������� ����������� �����; ��� � ������� �������� 
�� �������� �����. (�� ����������� � ������ �������� �.~�.~ꀐ��, 
��������� � ����� �.~5.4.4, �������� ���� ����� ��� ������� ������.)

����� ������ ��������� ��������� �������, ��������� ��� �������� 
������� ��������. 񎎒����������� ������ ������� � � ����������� 
����������. ��������� ����������� ���������� ��� "��������������" � 
����������� �� ����, ����� ������� ��������� � ������. �� ����������� 
���������� � �������� �������, ����� ��������� ������� ���� ��������� �� 
������ �������, � ���������---�� ��������, ��� ����� ������ ������������� 
������� ��������� ������� � ����������� ������� ����� \emph{���������} � 
�������������� ��������, �� ��� ������ �� ����� \emph{��������������} 
���������. (�. � ���.~6.)

\emph{����������} ���������� �������� ����� ����� ���� ���� � ���� 
��������������. � \emph{������������� ����������� ����������} �� 
���������� ��������� �����, ���� �� ��������� ���- ������, ���������� 
������ ���� ���� ��� ���������� �����, ����� ����������� ���������� 
����������; ����� �������� ����������� � ������������ �� �������� �����, 
����� ������� ���������� ��������������. 퀏�����, ���� ������� ��� 
������� ����� � ���� �������� � ���� ����� �������� ��������� �������, 
�� ����� ������ � ����, .��� �������� ����� ���� `$0x$' �� ����� T1, � 
����� `$1x$' �� ����� T2. 呋� �� ����� T1 �������� ������ �������, ��� 
������� ������, �� ����� ������������� �� � �������� `$00x$' �� T2 � 
`$01x$' �� T�. 򅏅��, ���� ������� `$00x$' ���������� ��������, 
���������� ���������� ���������� ��� � ������� ���������, � ����� 
�������� ��������� �������� `$01x$'. ����� ����� ��� 
������ �.~X.~������� "��������� ����������������� �����������" [{\sl 
JACM\/}, {\bf 3} (1956), 157--159]; ����� �������� ��� 
����������� X.~흃��� [{\sl JACM\/}, {\bf 6} (1959), 459--468], ������� 
��� ��� ��������� ��� "����� ���������� ����", � �. X. ㎄��� 
[{\sl IBM Tech. Disclosure Bull.\/}, {\bf 12} (April, 1970), 1849--1853].

%% 416
\qsection �������� �� ����������� ���������� �������? �� ������ 
���������� �������� �������������� �������� ��, ��� 
\emph{����������� ���������� ������ ���� ���������� ��������}. 
��� ������� � ���, ��� ����� 
������ � ���������� ���� ���������� �������� ������������ ������������: 
��� ���������� ���� ��� ��������� ����������� ����������, ����� ����� ���� 
������������ ���������� ����������, ���������� ����� ����� ������� 
������ �� ���� ���. � ����� ���� ������������� ����������� ���������� 
����� ����� ��������� ��������, ��������� ������� ������� ������, ��� 
��� �� ����� ������������� ������������� ������ �� ����������� ������� 
������ ������� �����, ��� ���� �� ��� ������������� ������� � ������ � 
����������. 񎎒���������� ���������� ����� �������� ���� ������ (�. �.
 ����� ����������). (�. ���. 5.3.1--33.)

䋟 ������� ����������� ���������� ����������, ������, ���� ������ 
����������. ��������, ��������, ��� ������� ����, ���������� ������� 
���� ����������� �������� ����������� � ���������� �������; ����������� 
������� �� 10 ���������, � ��������� ������������� ���� ���� �� 
����������, \emph{��������} ���������� ������� ����������� � ������ 
���������. 呋� ���� �������, �� �� ����� ���� ������� ��� ���������, 
��� ������� ��������� ���������� ����������� ����������, ��� ��� ����� 
�������, ������������� ������� �� 10 ���������, �����, ��������, ������, 
��� ����� �������, ������� ���� �� � ��������� ��������, ���������� 
������� � ����������. ⎎��� ������, ���� �������� ������ ��� ���, ��� 
����� ������� � ����������� ������� ����� ��� ����� �������� 
����������� ������, �� ������� ������������ ����������� ����������.

� ������ � �.~5.2.5, ��� �� ��������� ���������������� ��� 
\emph{����������} ����������� ���������� ���������������� �������, 
��������� "���������� ����" ����������� ���������� ��������� ��� ������� 
���������. 呋� ������� ������ ����� �������, �� ��� ����� ����� ����� 
��������� ��������� ��������� ������� ������ � ����� ���������, 
����� ������ �� ������������� �����/������. ���� � �������� �������� 
����������� ����������, ��������, ����� �������, �������� ���� ��������, 
��� ����� ���������� ������������.

\excercises
\ex[20] ወ�� � ������ �. 5.4 ���� ���������� ����� 
���������������� ������� �� $T$ ������ � ���������� $P$, $1 \le P < T$. 
�����, ��� ��� ������������� ����������� ����������, ������������ 
������� ��������� �� ��������� ����������.

\ex[�28] � ������ ������������ ������������ ����������� 
����������� ���������� 21 �����! ����� �� �� ������ $F_n$ ������; 
���������, ����� ����� � �� ����� ����� ����������� � ����� ������ ����. 
[{\sl 󊀇����:\/}
%% 417
����������� ������� ���������, ������������ ����� 􈁎�����; 
���. 1.2.8-34.]

\ex[�40] �������������� ���������� ���.~2 �� ����������� ����������� 
���������� � �������� ��� ������� ����������� ���� (��. � ���.~5.4.2--10).

\ex[�20] 䎊�����, ��� ����� ������������� ���������� ������ ��������� 
�������� ���������� 10 ������ �� ������� ������ ��� ��������� ������ � ��� 
������, ��� ��������������� ������ ����� ����������� ����� �������� ���� 
����� ���� "������� 4-fifo ��������". (򀊈� �������, ���, �� ��������, 
��������� �����, ���� �� ��������� ����� ���������.)

\ex[15] 퀐������ 4-lifo ������, ��������������� ����������� 
���������� 쎗�� � �������� ������� 10 ������.

\rex[20] 텊������ ���� �������� ������������� ����� $00$, $01$, \dots, 
$99$. �� ���������� ����������� ��������� 쎗�� �� ����� ������ �� 
����� ��������� �� �� ����� �� ����� ��������, ������� ������ ����� 
$T2$ � $T4$. � ����� ������� � ����� ������ �������� ����� �� $T2$?

\ex[21] ����� �� ������� �������������� ����� � � ������ �� 
���������� �������?

\subsubchap{񎐒������ � ����� �������}
䋟 ���� ����� ��� ���������� ������� �� ���� ����������� �������� ����,
 ���������� ��� �����. 荒������ �������� � ���, ��� ����� �������� 
������� ��������� ������� ���������� � �������������� ������ ���� ����.

� 1956~�. �.~�.~䅌�� ��������� ����� �����, �������������� ����� 
���������� ������ � ���������� � ���������� ������� ��������. 
��������, ��� �������� ������ �������� ����� $T1$, � ������ � ����, 
��� ��������� � ������ $P+1$ �������. 򅏅�� ������� ������ � 
���������� ������ �� ����� $T2$ � ������� �� ��������� �������� �������. 
������� �������� ������, ���� ������� � ������� ������ ���������� � 
������, �������� ������ ������ ��� ������������ ������� �� $P+1$ ���������.
 ꎃ�� ���� ������� �����������, � ������ �������� ���������� $P$ 
������ �����; ������� �� � ������������ �������. 򅏅�� ���������� ��� 
����� � �������� ���� �������, ����� � $T2$ � ��������� �� $T1$; ������ 
����� ������ �������� ��� �� ������� ���� $P$ ������� �� ���� �����. � 
��������� ����� �������� ������� �������� ��� ����������� �������, ����� 
���� ���� ������ �������������. �������� �� �����  
$\lceil(N-1)/P\rceil$  ��������.

숍����� ����������� ����������, ��� ������ ������ ���� ��������� 
������������ $P$ ���������������� �������� ���������� ������� �������� 
(�������� 5.2.2�)! 呋� ������� ����� $P$ ��� ����� ��������, �� ��� ����� 
�� �������� ������ ���� ��������� � ������ � ������� ����� ���������� 
������� (�������, ����� �������, $P$ ��������). 呋� ������� ����� ����� 
$P$ ��������, �� �� �������� � ������ ������ � ����� ������� ������ ���� 
������� ������ (�������, ����� �������,
%% 418
��� ���� ��������). 呋� $P=1$, �� ���������� �� �� �����, ��� � � ������ 
��������, �� ������� 5.2.21.

�� ����� �������� �����, �������������, ����� $\lceil I/P \rceil$, ��� 
$I$---������������ ����� �������� ������ ��������. � ������, �������� � 
�.~5.2.2, ������� �������� $I$ ���� 
$N-\sqrt{\pi N/2}+(2/3) +O(1/\sqrt{N})$.

呋� ���� �� ������� ������ ����������� ������ ����������� ������ ��� 
���� �� ������������� ����� ����������, �� ��� ���������� ������� �������� 
$P$-�� ������� ����� �������� �������; � ���������������� �� ����� 
����������� ���� � ��� ������, ����� ������� �������������� 
�������������� ����������, ��� ��� ���� ������� ���������� ����� 
����������� ������, ��� �������� ������ ���������� ������ �����! � 
������ �������, ��� ����� �������� ������ �������� ��� �������� �������� 
������� �� ��������� ������������� ���������, ��� ��� ����� �� ������ 
�������������� ��������������� $N^2$.

������, ��� ����������� ���� ����� ��� 100000 ������� � ������� �� 
�.~5.4.6. 퀌 ����� ������� ������� $P$, ����� ������ ���������� 
���������� ��� ���������� �������� ������ � ������ � ������������. � 
��� � ������� ��������������, ��� ������ ������ ����� ����� 100 �����, 
� 100000 ����� ��������� ������, �� � ��� ����� ����� ��� ���� ������� 
����� � ���� ������� ������ ������� $B$, ���� ������� �������� $P$ � $B$, 
�����, ���
$$
100 (P+1) +4B =100000.
\eqno(1)
$$
呋� ������������ ����������� �.~5.4.6, �� ��������������� ����� ������ 
������� ������� ���������� ���
$$
NC\omega\tau(1+\rho), \qquad \omega=(B+\gamma)/B.
\eqno (2)
$$
������ ����� �������� ������� ��������������� $P$, �� ����� ������� 
����� $B$, ������� 100, ������� ������������ �������� $\omega/P$. 
������������ ������ ����������, ��� �������
�����������, ����� $B$ ����� �������������� 
$\sqrt{24975\gamma}+\gamma^2-\gamma$. ���� �� �������� $B=3000$, $P=879$.
 ���� � ����������� ���� �������� $N=100000$, ��������, ��� ����� 
�������� $\lceil I/P\rceil$ ����� .����� 114, �. ������ ������ ������� 
������� ���������� �������� $8.57$~� (����������� ��� ��������, 
��� �������� ������ � ������������� ����� ����� ����� $B=3000$). 焅�� 
����������� ������, ����� ������ �������� ����� $0.44$ ������; ������ 
������ ����������� �� �������� � ���� ��� ������ �������. 쎆�� ���������� 
��������� ���������, ������������ � ��������� ������������� ���������� � 
��������� ������� � ����������� ������� �� ��������������� 
%% 419
�����, ������� ����� ���������, ��������� ��� ������ ������ 
���������� ���� � ������� ����� ����, ��� ��� ��� ��������� �� ����� ������.

\section ������� ������� ����������. 噅 ����� ������� ���������� 
����������, ������� �������� ������ ����� ���������������, �������� 
�������� ���������� � ����������� ��� ������� ���������� (�������� 5.2.2Q) 
쎆�� �� �� ������������ � ���� ������? [N. �; Yoash, {\sl CACM\/}, {\bf 
8} (1965), 649.]

텒����� ������� ��� ����� ������� ���, ���������������� �������� �������. 
��������, ��� ��� ����� �������� 0 � 1, � ����������, ��� ���� 
������������� ��������� �������:
\picture{������������ ����� �� �����, ���. 419}
ꀆ��� ����� ��������� � �������� �����. 䂅 ����� ������, ������������ 
��� ������������ �����, ���� ����������� ������� ���� �������� �������, 
� ������� �� ����� ���������� ������� ������� ����� ��� ������, ������� 
�������� �� ������ ����� � ������. 񋅄����� ����������� ������������ 
���������� ��������������� ��������� ����������.

\itemize
\li \strong{SORT00} [������������� ������� ������� � ����� $0$ � ������� 
��� �� ����� $0$]. 呋� ������� ���������� � ����������� ������, �� 
��������� � ���� ���������� ���������� � ����� ������� ��� �� �����. � 
��������� ������ ������� ���� ������ $R$ �� ��������; ����� �� ������ 
����� $K$. ����� ����� $0$ � �������� �����������, ���������� ��� ������, 
����� ������� $>K$, ������� ����� ������� ����� "�������" ������� �� ����� 
$1$. 򅏅��, ����� ����� $0$ � ������ �����������, ���������� ��� ������ 
� �������, ������� $K$, �� ����� $1$. 瀒��, ����� ����� ����� $0$ � 
�������� �����������, ���������� ��� ������ � ������� $<K$ �� ����� 1. 
⛏������ \strong{SORT10} ��� ������� $<K$, ����� ����������� �����, 
������ $K$, �� ����� $0$ �, �������, �������� \strong{SORT10} ��� ������� 
$>K$, ��������� ����������.

\li \strong{SORT01} [������������� ������� ������� � ����� 0 � �������� 
��� �� ����� 1]. ���������� \strong{SOR�00}, �� ��������� ��������� � 
\strong{"SORT10"} �������� �� \strong{"SORT11"}, �� ������� 
������� ����������� ������  $\le K$ �� ����� 1.

\li \strong{SORT10} [������������� ������� ������� � ����� 1 � �������� 
��� �� ����� 0]. 򀊀� ��, ��� \strong{SORT01}, �� �������� ������� 0 �~1, 
� ����� ��������� ��������� $<$ �~$>$.
%% 420
\li \strong{SORT11} [������������� ������� ������� � ����� 1 � ������� 
��� �� ����� 1]. 򀊀� ��, ��� \strong{SORT00}, �� �������� ������� 0 � 1, 
� ����� ��������� $<$ � $>$. 쎆�� ��� ����� ���������� � ����������� 
�������� ���� ��������, ��������� ���������� ����������� ���������� �� �����.
\itemend

呋� �������, ��� ������ ��������� � ��������� ������� � ����������� 
������ ������ ������������ ����, �� ����� ������� ����� ������ ����� 
��������� ��������� �������. �� $M$---����� �������, ������������ � 
����������� ������. �� $X_N$---������� ����� �������, �������� �� ����� 
���������� \strong{SORT00} ��� \strong{SORT11} � �������� �� $N$ �������,
 ��� $N > M$, � ����� $Y_N$---��������������� �������� ��� 
\strong{SORT01} �~\strong{SORT10}. 򎃄� �����:
$$
\eqalign{
 X_N&=\cases{
  0, & ���� $N\le M$,\cr
  3N+1+{1\over N}\sum_{0\le k<N}(Y_k+Y_{N-1-k}), & ���� $N>M$,\cr
 }\cr
 Y_N&=\cases{
  0, & ���� $N\le M$,\cr
  3N+2+{1\over N}\sum_{0\le k<N}(Y_k+X_{N-1-k}+k), & ���� $N>M$.\cr
 }\cr
}
\eqno(3)
$$
������� ���� ������������ ����������� (��. ���. 2) ����������, ��� ����� 
����� ����������, �������� � ����� � ������� ��� �������� ����������, � 
������� ����� $6{2\over 3}N\ln N+O(N)$
��� $N\to\infty$. � ����� ����� �� ������� (5.2.2--25), ��� ������� ����� 
��� ���������� ���������� ����� ����� $2(N+1)/(M+2)-1$.

呋� �� �������� ���� ������ � ������� 100000 �������, �������������� � 
�.~5.4.6, ������ ������������� �������� �� 25000 ����� � ����� �������, 
��� ����� ���������� �������� �� $n\le M=1000$ ������� ����� 
$2nC\omega\tau$, �� ������� ������� ����� ����������, �������������� 
������ 103 ��� (�������, ��� � ����� �, ������������� ���������). 蒀�, 
����� ������� ���������� � ������� ������; ��, �������, � 
\emph{���������} ������ �� ������ � �������� ���� ������ ��������, 
�������������� ����.
\section �������� ����������. ����� ����������� ����������
(�������� 5.2.2R) ����� ����������� ������� ������������ ��� ���������� � 
����� �������, ��� ��� �� ����� ����� �� ������� ����������. � �������� 
�����, ������� ��������
��������� ��� ��� ������, �������������� ���� ������ ����� ����� ��� ���� 
���---��, ���� �� ������� �� ������ � ���������� ���������� ��� ����.

%% 421

� ������� ���� �� ����� ����� ����������� ������� ����������� 
���������� �� ���� ������ "�������-��-�������-�����". 茅� �������� 
������ �� $T1$, �������� �� $T2$ ��� ������, ���� ������� � �������� 
������� ������������ �� 0;
����� ����� ��������� $T1$ ������ �� �����, ������� ������ � �������, 
��������������� �� 1. 򅏅�� �������������� ��� ����� � ����������� 
����������� ���� ��������, �� � ������� $T1$ �� $T2$ � �������������� 
\emph{�������������} �������� �����. � ���� ������ $T1$ ����� ��������� 
��� ������ � ������� $(\ldots00)_2$, �� �������� ������� ������ � ������� 
$(\ldots01)_2$, ����� $(\ldots10)_2$, ����� $(\ldots11)_2$. 呋� ����� 
����� ������ $b$ �����, ��� �����������, ����� ��������� ����������, 
������ $2b$ �������� �� ����� �����.

����� ����������� ���������� ����� ��������� ������ � \emph{�������} 
$b$ ����� ����� ��� ���������� ������� ���������� ����� $b$; ����� 
�������, ����� �������� ���������� �������� � $2^b$ ���, ���� ����� ���� 
���������� ������������; � ����� ��������� �������� $P$-������� ���������� 
������� �������� �������� ��������� ������.

펂��, �� ��������� ����� ������� ������ � �������������� ���������� � 
����� ������� ���������� �. �. 툊���� � �. �. ������ [{\sl 
ꈁ��������\/}, {\bf 2}, 6 (1966), 79--84]. 茅���� �������� ����� ������ 
�� ������ �� ������ ��������� ������������ ������� �����, � �� ������ 
���� ��������� �������� ������������� ����� $\kappa_1$, $\kappa_2$, 
\dots, $\kappa_M$ ���, ����� ��� ������� $i$ ����� �������������� ������, 
������� ����� $\kappa_i$ � $\kappa_{i+1}$, ���� ����� ������� 
������������� ��������� $P_1$ � $P_2$. 򀊈� �������, $M$ ����� ����� 
$\lceil  N/P_1 \rceil$ � $\lceil N/P_1\rceil$. 呋� �������� ������� ����� 
�� ���� ����������� ���������� ��� ����������� ����� $\kappa_1$, 
$\kappa_2$, \dots, $\kappa_M$, �� �������� ��� ���� ��� ��������� 
�������� ��� �������� ������� ������������ ����� �������� ����� ��� 
��������� ������������� ������� �����. �� ���� ��� ������� 
������������� ������ ���������, $2\lceil \log_2 M \rceil$  �������� ����� 
���������� ��� ���������� ����������. (���� ����� ������� ������������ 
������, ����������������� $N$, � ������� �� ����� �������������� ��� 
������� ���������� ��� $N\to\infty$. � �������� �� �� ������ ������������ 
���� ����� ��� ������ �� ���������� �������, �, �������������, $M$ ����� 
������������ ��������, ��� ��� ������� ������������� ������ ����� 
���������� � ������.)

\section 茈����� �������������� ����. �.~�.~����� � �.~�.~񒈐�� �������� 
����� ����� �������� $k$ ���� ����� �� ���� ������, ������ ����� �������, 
��� ��������� ��������� ����������� ����� ���������� ����� ���� � $O(\log 
L)$ ���, ��� $L$---������������ ����������, ������� ����� ������ �� ����� �����
%% 422
����� [{\sl JACM\/}, {\bf 13} (1966), 533--546]. � ���������� � 
������ ���������� ����� ������ ���������, ��� � ������� � ��������� 
������, ������������ �.~�.~ꀐ���.

ᓄ�� ����������� ������� ���������������� ������� �� ������� ������, 
��������� ��� �����: $T1$ � $T2$. � ������ �� ��� (�. �. �� $T1$) 
���������� ����������� ���� �������� ����� ��������, ��� ���������� �� 
���.~86; ���������� ����, ��� ������ �������� �� ������� �������� �� ����� 
��� ������ ����������� �����. (� ���������������� ����� �� ����� �����
\picture{���. 86. �������� ����� $T1$ � ����������� ����� � 񒈐���}
�������; �� ������ ����� $1$, $5$, $9$, $13$, \dots  ��� ������� $1$,
 ����� $2$, $6$, $10$, $14$, \dots ��� ������� $2$ � �. �.) 䐓��� ����� 
($T2$) ������������ ������ ��� ���������������� ��������, ����� ������ � 
���������� ������������ �� $T1$.

ዎ�� �� ������ ������� ����������� �� \emph{����}, 
���������� �������������� $1$, $2$, $4$, $8$, \dots, $2^k$, \dots ������. 
玍� $k$ �� ������ ������� ���� ��������� ����� $2^k$ ������� ������, ���� 
������� �����. 퀏�����, �� ���.~86 �� �������~$1$ ������ ���������� � 
�����~$1$ �~$3$; �� ������� $2$---� ����� $0$, $1$ �~$2$; �� ������� $3$---� 
����� $0$ �~$2$; �� ������� 4---� ����~$1$, � ��� ��������� ���� �����.

��������, ��� �� ������� ������ � ������� $1$ �~$2$ �� �������~$3$. � 
����������� ������ ��� ��������� ��� ������, ������������ ����������� 
�������� ��� �����, � ����� ������ �����---��� ������. ꎃ�� ����� ����� ��� 
�������~$1$ ������ ������, ����� ��������� ��� ��������� �������: ����� 
������ �������� ���� �������~$1$, ������ ���� $k$, � ����������� ������ �� 
���� � ����� �����, ����� ����������� ��������� $2^k-1$ ������ ������ �� 
$T2$ � ����������� �� � ���� 0, 1, \dots, $k-1$ �������~1. (򅏅�� ���� 0, 
1, \dots, $k-1$ ���������, ���� $k$ �����.) ����������� ��������� 
������������ ��� ���������� ������ ����� ��� �������~2, ��� ������ �� 
������ ������. ꎃ�� ����� ������ ����������� ��� ������ �� �������~3, 
�� �������� ���� �������, �. �. ������������� $T1$ ���� �� �������� ������ 
\emph{������} ���� �� �������~$3$, ������ ����~$k$, � � �� �� ����� 
�������� ������ �� ��� 0, 1, \dots, $k-1$ �� $T2$. 䀍���
%%423
�� $T2$, � ������� �������������� ���������� ������ ������, ������������ 
������ ��� ���������� ���� $k$ �� ������� 3.

䋟 ���� ��������� �� ������ ����� ������ � �������� ����� $T1$, �� 
�������� ����������� ���������� �� ���� �����. ꀊ � � ������ 
������������� ���������� � ������ ������� (�.~5.4.5), ����� ��� �������� 
��������� ��� ��������, ���� ������� ���� ����������������.

������ �������� �� ���� $k$ ����������� ������ ���� ��� �� ������ $2^k$ 
�����, ��, ����� ���������� $2^i-1$ ������ � ������� 1 � ������, 
����������� ����������� ����� �� $\sum_{v\le k<l} 2^{l-1-k}\cdot c \cdot 
2^k=cl2^{l-1}$, ��� $c$---��������� ���������. 򀊈� �������, ������ ������ 
������� ������� $O(N\log N)$ �����. � ��� � ���������������� ������� 
������� $O(\log N)$ ��������, �� ����� ����� ������ ����� $O(N(\log 
N)^2)$, ��� �������������� ����������� �����, ��� ��������� ������ ��� ������� 
����������.

� �� ����� ���� ���� ����� ����������� ����� �����������, ���� 
����������� ��� ���������� 100000 ������� �� ������� �.~5.4.6, ��������� 
����������, ������� ������ ����������� �� ����� $T1$, �� ��������� �� 
����� ������ �����. � ���� ���� �� ����������� ���� ������ � ����� 
�������� �� ����� ��������������� ������������� ������������ ���������� 
������/������/����������, ������������ ���� ���������� ����������� � �. �.,
 �� ������, ��� ��� ���������� ���������� ����������� ����� 37~�! 蒀�, 
���� ����� ������������ ����� ������������� �������: ��������� � 
$O(N(\log N)^2)$ ������� ������, ����� ����� ��� ���������������� ��� 
������������ �������� $N$.

\section ���������� ����������. 쎆�� �� �������� ����� ����� ������? 
텒����� ������, ��� ���������� ������� �������� $P$-�� ������� ����� 
������������� � ������������� ����������, �� ��������� ����� ������.

�.~�.~䅌�� [Ph.~D.~thesis (Stanford University, 1956), 85] ������ 
����������, ��� � �������������� ������ � ������������ ����������� 
������� ������, ��������� ����� �������� ������������ ������, ��� �� 
������������ ��������, ����� ��������� ����� �� ������������ ����������; 
�������������, ����� �������� ���������� � ����� ������ ��������� � 
������� �� ������� ���� $dN^2$ ������ ������� (��� $d$---��������� 
������������� ���������, ��������� �� ������������ ���).

�.~�.~ꀐ� ����� ����� ���������� ������ � ������������. ���� ����, 
��������� ��, ���, �� ��������, �������� \emph{�����������} �������� 
���������� � ����� ������.  ���������� ��������� ꀐ�� ������ 
��������� ������� ����������������� ������: \emph{��� ������� ����� 
��������� ����� ����� �������, ���� �������� ������ ���� ����?}

%% 424

���������� ������ � $n$ �������; ��������� ������� ����� ���������� �� $c$ 
�������. � ���� ������ ��� �� ����, �� ������, �� �������, �� ��� �� ���� 
����, ������� ����� ��������������� �� ����� �����. � ������ ��������� 
$cn$ �������, � ����� $c$ �� ��� ����� ������� �� ������ ��������� ����. � 
���� ��������� ����� ������� $b$ �������, � �� ����������� ���� ������� 
������� ��� ����������� � ����� $i$ �� ���� $i+1$. � ������ �� ����� 
���������� ������ ����������� ���� ����� �� ������ �����, ���� ���������, 
����� ���� ����� � �������� ���� �������� �� ������ �����.

텒����� �������� ����� ����� ���� ������� � ������������� �����������: 
����---��� ������, ������---�����, �����--- ���������, ����� �� �����, � 
����---����������� ������ ���. 䅉������ �������� ��� ��� ����������� 
������� ��������, ��� ��������� ������� (��� �����, ��������, ��������� 
��������� ���, �������� �������� �� ��� �����, �������� �� �� ����� �� 
������ ������ � �. �.); �� � ���������� ���� ��������� ������ �������� 
���������� �������� �������� ��� ���������� ����� ��������. �������� ꀐ�� 
���������� ��������� ��� ��������������� �������:
$$
\eqalign{
u_k, 1\le k\le n:& 
\rem{����� ����� �� ������  $\le k$, ����������� ������� �� ����� $>k$}\cr
d_k, 1\le k \le n:& 
\rem{����� ����� �� ������ $\ge k$, ����������� ������� �� ����� $<k$}\cr
}
\eqno(4)
$$.
ꎃ�� ���� ����, �� ������ ����� $u_k=d_{k+1}$ ��� $1\le k < n$, ��� ��� �� 
������ ����� ��������� $c$ �������; ���������� �����, �������������� � 
������ $\{1, \ldots, k\}$ �� ����� $\{k+1, \ldots, �\}$, ������ ��������� 
����� �����, ����������� ������������� � �������� �����������. � 
����������� $u_n=d_1=0$.

ߑ��, ��� ���� ������ ������� �� ������� ���� $\lceil u_k/b\rceil$ ������ 
� ����� $k$ �� ���� $k+1$ ��� $1\le k<n$, ��� ��� ������ $b$ ���������� 
����� ��������� �� ���� ����. ����������, �� ������ ������� �� ����� 
$\lceil d_k/b\rceil$ ������ � ����� $k$ �� ���� $k-1$. 񋅄���������, 
����� ����������� �� ������� ����
$$
\sum_{1\le k\le n} (\lceil u_k/n\rceil+\lceil d_k/b\rceil)
\eqno (5)
$$
������ ������� ��� ����� ���������� ������� ������. ꀐ� ���������, ��� 
��� ������ ������� ������������� ���������, ���� $u_1$, \dots,  $u_{n-1}$ ���������.

\proclaim 򅎐��� �. 呋� $u_k>0$ ��� $1\le k <n$, �� ���������� 
������ ������ �����, ��� ������� ��� ���� ������������ �� ���� ����� �� 
����������� ����� (5).
%%425

\bye