\input style
%% 188

�� $s_l$---������ ��������� � ������~$l$, 
�~$M_N$---���������������~$\{s_1, s_2, \ldots, s_N\}$ ���� ���� ��������. 
葏������ (14) � (15), ����� ���������~$M_N$ ��� ����� ��������~$N$. � 
���.~5.1.4--20 ��������, ��� ����� ����� �������� ��������� �������� 
�� ����� ����� $\{1, 2, \ldots, N\}$ �����
$$
N!/s_1s_2\ldots s_N= N!/\prod_{s\in M_N} s.
\eqno(16)
$$
퀏�����, ����� �������� ����������� 26 ���� $\{A, B, C, \ldots, Z\}$ �� 
���.~28 ���, ����� �� ��������� ���������� ���������� �������, �����
$$
26!/(26 \cdot 10 \cdot 6 \cdot 2 \cdot 1 \cdot 1^{12} \cdot 3^6 \cdot 7^2 
\cdot 15^1).
$$

򅏅�� �� � ��������� ���������������� ���� ���������� �������� � 
���������~H, �. �. ����������, ������� ����������� �� ����, ��� � ���� H2 
������� ���������� ������� $l=1$. � �������, ��������� ��������� ���� 
������� ������ ���������� �������� ����� ������ � �������� ����������� �������� �������������.

\proclaim 򅎐��� H. 呋� ��������� ������� ��� ��������� H 
������ ��������� ������������ ��������� $\{ 1, 2, \ldots, N\}$, �� � 
���� ���������� �������� � ���������� ������������ ����� ���������� 
����� �� $N! /\left(\prod_{s\in M_N} s\right)$ ��������� �������. ᎋ�� 
mo��,
��� $\floor{N/2}$ �������� �������������, ����������� �� ����� ���� ����, 
"����������" � ��� ������, ��� �� ���������� ���� H8 ��� $s_l$ ��������� 
�������� ����������~$i$ �������������.

\proof ����� �����, ������� � ��������� ������� ���������� ������� 
"�������� ������". �� � �������� ������ �� ��������� ����������� 
�������� ������������� ������ �������� $K_1$ \dots{} $K_N$ � ������ � 
����~$l$; ����� ����, ��� ������� �����~$s_l$ �������� ������������ $K'_1$ 
\dots{} $K'_N$ �����, ������� ����� ������������� ���� ����� ���������. 
⑅ ��� �������� ������������ ����� ��������� �������� $K'_l$, 
�������������, ��������� � �������� �����������, ���������� ����� $s_l$ 
$s_{l+1}$ \dots{} $s_N$ �������� ������������ ��������� 
$\{1, 2, \ldots, N\}$, ������� ����� ���������� �������� ������������� � 
�������~$l$ ���� ������������ $K_1$ \dots{} $K_N$.

񋓗�� $l=1$ �������: ����� $K_1$ \dots{} $K_N$---��������, � ����� $K'_1$ 
\dots{} $K'_N$---����, ������� ������������� � $K_1$ \dots{} $K_N$ � 
���������� ������������� ��� $l=1$, $K=K'_1$. 呋� $K=K_i$, �� ������
����� ����� ��������� $K'_i=K_{\floor{i/2}}$, 
$K'_{\floor{i/2}}=K_{\floor{i/4}}$ � �. �., ��� ���� $K'_j=K_j$ ��� ���� 
$j$, �� ������� �� ���� ��~$1$ �~$i$. ����, ��� �����~$i$ � ���������� 
������ ���������� ���������� ���� $K'_1$ \dots{} $K'_N$, �����, ��� (a) 
�������� ������������� �����������
%% 189
���� $K'_1$ \dots{} $K'_N$ � $K_1$ \dots{} $K_N$ � 
(b) $K_{\floor{j/2}}\ge K_j$ ��� $2 \le \floor{j/2}<j\le N$. 
񋅄���������, �������� �����~$N$ 
����� ������ $K'_1$ \dots{} $K'_N$,  � �������� ������������� ����������. 
(��� �������������� ���� ������� ��. � ���.~22.)\proofend

������ � ��������� $A$, $B$, $C$, $D$ � ������� ���������~H, ����� 
������, ��� ����������� �������� �������������, ������������ ��� 
���������� �������~$s$, ���� ����� $\floor{s/2}/s$ � ������� �������� 
��������~$A$; �� ����� � ������� �������� ��������~$B$ �����
$$
{1\over s}(0+1+1+2+\cdots+\floor{\log_2 s})=
{1\over s}\left(\sum_{1\le k\le s} \floor{\log_2 k}\right)=
{1\over s}((s+1)\floor{\log_2 s}-2^{\floor{\log_2 s}+1}+2)
$$
(��. ���. 1.2.4--42); � ��� ���� �����~$2/s$ ���~$0$ � ������� �������� 
��������~$D$ � ����������� �� ����, �������� ��~$s$ ������ ��� ��������. 
텑������ ������� ���������� ��������������� ����� � ������� �������� 
��������~$C$, ��� ��� ��� ������ ��������������� �������� (��. ���.~26). 
������ ������������ �� ���� ��������� �������������, �������, ��� 
������� �������� ��������~$A$ �� ����� ���������� �������� �����
$$
A'_N=\sum_{s\in M_N} \floor{s/2}/s;
\eqno(17)
$$
����������� ������� ����� ����� � ���~$B$, $C$ �~$D$, ��� ��� ����� ��� 
������� ����� ����� ��������� ��� ������� ��������. � ��������� ������� 
��������� �������� ����������:
\ctable{
\hfill\bskip$#$\bskip&&\hfill\bskip$#$\bskip\cr
N\hfill & A'_N\hfill & B'_N\hfill& C'_N\hfill & D'_N \hfill\cr
  99 &  19.18 &  68.35 &  42.95 & 0.00 \cr
  100&  19.93 &  69.39 &  42.71 & 1.84 \cr
  999&  196.16& 734.66 & 464.53 & 0.00 \cr
 1000&  196.94& 735.80 & 464.16 & 1.92 \cr
 9999& 1966.02& 7428.18&4695.54 & 0.00 \cr
10000& 1966.82& 7429.39&4695.06 & 1.97 \cr
10001& 1966.45& 7430.07&4695.84 & 0.00 \cr
10002& 1967.15& 7430.97& 4695.95& 1.73 \cr
}
��� �������� �����������, �� �~$M_N$ ����� �� �������� �������� �� 
������� ������ �����������, � ����� �� ������, ��������, ���
$$
A'_N={N\over 2}\cdot{0\over1}+{N\over 4}\cdot{1\over3}+
{N\over8}\cdot{3\over7}+\cdots+O(\log N)=
\left(1-{1\over2}\alpha\right)N+O(\log N),
\eqno(18)
$$
%% 190
���
$$
\alpha=\sum_{k\ge 1} {1\over 2^k-1}=
1.60669\ 51524\ 15291\ 76378\ 33015\ 23190\ 92458\ 04805\hbox{---}.
\eqno  (19)
$$
(��� �������� ������� �.~�.~���� �������, ��������� ��������������� 
���� �� ���.~27.)  �������~$N$ ����� ������������ ������������ �������
$$
\eqalign{
A'_N&\approx 0.1967N+0.3 \hbox{ ($N$ ���.)}, 
  \quad 0.1967N-0.3 \hbox{($N$ �����.)};\cr
B'_N&\approx 0.74403N-1.3\ln N;\cr
C'_N&\approx 0.47034N-0.8\ln N;\cr
D'_N&\approx 1.8 \pm 0.2 \hbox{ ($N$ ���.)},
  \quad 0 \hbox{($N$ �����.)}.\cr
}
\eqno(20)
$$
텒����� ���������� ����� ������������ � ����������� ��������. 䋟 
���������� �������� ��������� ����� $O(N)$ ����� (��. � ���.~23).

����, �� ��������, ����������� ������ ���� ���������� �������� � 
���������~H. ������ ���� ������---������ ������ ������, ������� ��� ������� 
������ �������! �� ������������� ���������� ����������� � 
$N$~���������; ��������� ����� $A''_N$, $B''_N$, $C''_N$ �~$D''_N$ ������� 
�������� ������� $A$, $B$, $C$ �~$D$ �� ����� ���� ������. ������ 
���������~H ���������� ������������ ����� ���������� ����� ����������� 
������������� ������� ��������
$$
\eqalign{
A''_N &\approx 0.152N;\cr
B''_N &\approx N\log_2N-2.61N;\cr
C''_N &\approx {1\over2}N\log_2N-1.4N;\cr
D''_N &\approx \ln N\pm 2;\cr
}
\eqno(21)
$$
��� �� ����� �� ��� ��� �� ������� ����������� �������������� ���������� 
���� ����������. ���������� ��������� �������� �������������, �������� 
������� ������� ������, ��������� � ������������ (8), ����, ���� 
������������� �������� ��� �����, ������� ������ ���~$C$, ��-��������, 
������� ���������
�������������� ��~${1\over 2}N\log_2 N$.

\excercises
\ex[10] ߂������ �� ���������� ����������� �������� ������ (�������� S) 
"����������"?

\ex[15] ��� � ��������� S ����������� ����� ������� �������� ������� 
���������� �������, ����� ���������� �� ���������� � �. � , ������ ���� 
����� �������� ������� ���������� �������, ����� ���������� �� 
���������� � �. �.?

%% 191
\ex[�21] (a) 䎊�����, ��� ���� �������� S ����������� � 
��������� ������������ ��������� $\{1, 2, \ldots, N\}$, �� � ���������� 
������� ���������� �����~S2 �~S3 ���������� ��������� ������������ 
��������� $\{1, 2, \ldots, N-1\}$, �� ������� �������~$N$. (荀�� ������, 
���� $K_1$ \dots{} $K_{N-1}$ � ���������� ������������ ����� ���� ����� 
������������� ��������� $\{1, 2, \ldots, N-1\}$.) (b) 񋅄���������, ���� 
����� $B_N$ ���������� ������� �������� ��������~$B$ � ���������~S, �� ��� 
�������, ��� �������� ���� ���������� ��������� �������, 
�����~$B_N=H_N-1+B_{N-1}$. [\emph{󊀇����:} ��. �� 
��������������� ���������������� 1.2.10--16.]

\rex[�35] � ����~S3 ���������~S ������ �� ��������, ���� $i=j$. He 
����� �� ����� ����������� ����~S3 ��������� �������~$i=j$? ���� ����� 
������� ����� ������� ���������� ������� $i=j$ � ����~S3, ���� �������� ���� 
�������?

\ex[20] ���� ����� �������� ��������~$B$ � ������� ���������~S 
��� ��������� ����� $N \ldots 3\ 2\ 1$?

\ex[�29] (a) �� $a_1$ $a_2$~\dots{} $a_N$---������������ ��������� $\{1, 
2, \ldots, N\}$ �~$C$ �������, $I$~���������� � �����, ��� ��� �� 
���������� � ������� ���������~S ������������ $B$~������� �� 
�������������� ��������. 䎊�����, ��� $2B\le I+N-C$. [\emph{󊀇����:} ��.
 ���.~5.2.2--1.] (b) �����, ���~$I+N-C\le\floor{n^2/2}$; �������������, 
$B$ �� ���������~$\floor{n^2/4}$.

\ex[�46] 퀉���� ��������� ��������~$B$ � ���������~S ��� ������� ��~$N$, 
������, ��� �������� ���� �������.

\ex[24] �����, ��� ���� ��� ������~$\max(K_1, \ldots, K_j)$ � ���� S2 
������������� ����� ����� �������: $K_1$, $K_2$, \dots, $K_j$, � �� 
��������: $K_j$, \dots, $K_2$, $K_1$, ��� � ���������~S, �� �� ���� ����� 
����� ���� �� ��������� ����� ��������� ��� ��������� ����������� 
����~S2. 퀏����� \MIX-���������, ���������� �� ���� ����������.

\ex[�25] ���� ����� ������� ����� ���������, ����������� ���������� �� 
���.~8 ��� ���������� ��������� �����?

\ex[12] ꀊ ����� ��������� ������, ������������ �� ���.~23, ����� ���� 
��� ����� ��������~14 ��~16 �������������� ���������?

\ex[10] ꀊ ����� ��������� ������, ������������ �� ���.~24, ����� ������ 
��������~$908$?

\ex[�20] 񊎋��� ��� ����� ��������� ���������~$-\infty$ �~$\infty$, 
���� ��������� "����������" �����, �������������� �� ���.~23, ��� 
������������ ����� �� $2^n$~���������?

\ex[20] (�.~�.~�.~󈋜���.) � ����~H4 ���������~H ����������� ��� 
������: $j<r$, $j=r$ �~$j>r$. �����, ��� ���� $K\ge K_{r+1}$, �� 
����� ���� �� ��� ��������� ���~H4, ����� ������������ ����������� ���� 
�� ���� �����. ꀊ ���� �������� ���~H2, ����� ���������� � �������� 
������������� ���������� ���������� ������� $K\ge K_{r+1}$?

\ex[10] �����, ��� ������� �������---������� ������ 
������������. (������, ����� ����� ����� ����������� ���������, ����� 
��������� "���������� �� ����������---������ �����������" ���� ������������ 
��������� "������ ����������---������ �����������".) ߂������ �� ���� 
����� ������� ������� ������������ �������?

\rex[M22] (�.~�.~������.) ������� ������� �������� ���������� ������� 
������� ����� $\le N$, � ������� ������������ \emph{������������ 
�������} � ����� �������� �������� �������. [\emph{󊀇����.} �� 
���������� ���� � ������������ ������� ����� ���������� �������� ��������� 
������, �������, ��� ����� ��������� �������� �����, ����������� ��� 
�������� � ������� �����. �������� ������ � �������� ����� ��������� 
� ���� �������.]

\ex[20] ������ ����������� ��������, ������� ��������� ����� ���� � 
������ �������� �� � ���������, �������� �������� �� $n+1$~���������.

\ex[20] �������� �� ���.~16 ����� ������������ ��� ���������� �������� 
������ ������ "���������� $l$ ��~$1$", ������������ � ���������~H.

%%192
������ �� ��� ������ �� ������ � ���� �� ��������� ����� ���� � �� �� ��������?

\rex[21] (�.~�.~􋎉�) � ����� ���� ������ � ��������� ������������� 
���������� ���� $K$, ��� �������, ��������� �������� ����� ��������, � 
������� ����� ��� ���� ���������� � ���� H6 ��������������, ��� 
$K<K_j$. ꀊ. ����� �������� ��������, ����� ���� $K$ �� ����������� 
�~$K_j$ � �������� ����� ����������?

\ex[21] ������� �������� ���������� ������� �������� �� �������� 
������� $N$, ����������� �������� �������~$N-1$.

\ex[�20] �����, ��� ������� (14) ������ ������� ������ ����������� ��������.

\ex[�24] 䎊�����, ��� ������� (15) ������ ������� �������� ����������� ��������.

\rex[20] ꀊ�� ������������ ��������� $\{1, 2, 3, 4, 5\}$ ���� 
���������� �������� � ���������~H ����������� � $5\ 3\ 4\ 1\ 2$?

\ex[�28] (a) 䎊�����, ��� ����� ����~$B$ � ��������� 
������������� ������� �� ��������� $\floor{\log_2(r/l)}$. (b) 񎃋���� 
������������ (8), �� ��� ����� ���������� ���������� ���������~H 
��������~$B$ �� ����� ��������� $N\floor{\log_2 N}$. 퀉���� ������������ 
��������~$B$ �� ������������ �������� ������ ��� ������� ��~$N$. (� 
������ ��������, ��� ���������� �������� ����, �� �������~$B$ ��������� 
��� ������������ ��������.)

\ex[�24] ⛂����� ������ ������� ������������ ���������� 
��������~$B'_N$ (��������� ����� ����, ����������� �� ������ �� ����� ���� 
���������� �������� � ���������~H).

\ex[�20] ���� ����� ������� ����� � �������� ��������~$C$ �� ����� ������ 
�������� �������������, ����� $l=1$, a $r=N$, ����~$N=2^{n+1}-1$.

\ex[�30] ������ ���.~25:  (a) ��� $N =26$, (b) ��� �������������~$N$.

\ex[�25] (�.~�.~����~��.) 䎊�����, ��� 
$\sum_{n\ge 1} x^n/(1-x^n)=\sum_{n\ge 1} x^{n^2}(1+x^n)/(1-x^n)$. [���� 
$x={1\over2}$, �������� ����� ������ ���������� ��� ��� ���������� (19). )

\ex[35] ������� ���� \emph{��������� �������}, ���������� �� 
������ ���������, � �� �������� ��������. ᓄ�� �� ��������� ������������� 
���������� ������� ��������?

\ex[26] (�. �. ᐀��.) ������ �������� ��������� ����������� 
��� ��������� 
�����~$(a_1x^{i_1}+a_2x^{i_2}+\cdots)(b_1x^{j_1}+b_2x^{j_2}+\cdots)$, 
������� �� �������� ������������ ������������ $c_1x^{i_1+j_1}+\cdots$ �� 
�������, �� ���� ���� ��� ������������� ������������ �������� 
�����������. [\emph{󊀇����:} '�������������� ���������� ������������ ��������.]

\ex[�48] 쎆�� �� ��������~$C$ ��������� ${1\over2}N\log_2 N$ ��� 
������������� ���������� �����? ���� ����� ������������ ��������~$C$? 
���� ����� ����������� ��������?

\ex[37] (�.~�.~�.~󈋜���.) �����, ��� ���� ��� �������� ���������� 
������� ���������� "��������� � ���������", �� ��� ���� 
����������� ������������ ���������, � ������� � ����� ������ ����� �� 
$O(\log n)$~����� ��������� ���� ����������, ���� ���������� �������. 
(򀊓� ��������� ����� ������� \emph{������������ �����}.)


\ex[21] ������������ �������� ������� ���� ���������������� ������������ 
��������, �������������� � ���� ������������� ��������, � ����. (� 
���������, ���� ���� �� ������ �������� �������� ����� ���� �������, �� 
��� �������� ����� ��������� ��� � ������ �������.) 

\rex[15] ��� � ������������ �������, �������������� � ���� 
�������������� ������, �������� �������� ����� ����������� ����� �������
%% 193
���� �����������, � �� "�����������" ����� �� ����������� � �������, ��� � ��������?

\ex[�47] 񊎋��� ����� ��������� ������������� �������� �� $N$~�����, ���� 
������������ �������� ����~|KEY|? [��� ������������������ ���������� � 
����� $1$, $1$, $2$, $4$, $8$, $17$, $38$, \dots; ���������� �� 
�����-������ ������� ��������������� �������?]

\ex[26] 呋� � ������������� ������ �~$N$ ������ �������� ����� |UP| (��. 
� ����������� �������� � ����� ������� � �.~6.2.3), �� ��� ���� 
����������� ��������� �� ������������ ������� ������������ ����~|P| 
��������� �������: ����� |LEFT(P)| �~|RIGHT(P)| � ��������� ���������� 
��������� �� �����~|P|, ����� ���������� ����~|DIST| � ������� ����~|P| �� 
��� ���, ���� �� ����� ��������� ���� ������, ���� ����, � �������� 
����~|DIST| �� ��������.

䎊�����, ��� ��� ���� ������� �� ����������� �������� ����� ��� $O(\log 
N)$ �����~|DIST|, �������� ���� �� ��, ��� ������ ����� ���������. ����� 
������� ���������� ����.

\ex[18] \emph{(瀌������ �������� ����� �������������� ��������.)} 
썎��� ������������ ������� ���������� �������� ���������� ����: ��� 
������� ����� ��������� ��� ��������---"�������������" ���� � ��������� 
�������� ����� "���������������" ���� ����� �����. ꀊ�� ��������� ������ 
��������� ���������� �������� ����� "���������������" ����?

\subsubchap{񎐒������ ��������} %5.2.4
\dfn{񋈟���} �������� ����������� ���� ��� ����� ������������� ������ � 
���� ������������� ����. 쎆��, ��������, ����� ��� ��������---$503\ 703\ 
765$ �~$087\ 512\ 677$, 
�������~$087\ 503\ 512\ 677\ 703\ 765$. ���� ������ ������� 
���---�������� ��� ���������� ��������, ������� ���������� �� ��� � 
��������� ��� ���������.

퀗�� �
$$
\left\{\matrix{
 503 & 703 & 765 \cr
 087 & 512 & 677\cr
}\right.,
$$
�������
$$
087\left\{\matrix{
503 & 703 & 765\cr
512 & 677 \cr
}\right.
$$
�����
$$
087\ 503\ \left\{\matrix{
703 & 765\cr
512 & 677\cr
}\right.
$$
�~�.~�. 텎������� ������������ � ��������� �� ������, ����� ����������� 
���� �� ������. ⅑� ������� �������� ������ � ��������� ���������.
\alg �.(䂓�������� �������.) ���� �������� ������������ ������� ���� 
������������� ������ $x_1\le x_2\le\ldots\le x_m$ 
�~$y_1\le y_2 \le \ldots\le y_n$ � ���� ���� 
$z_1\le z_2\le \ldots\le z_{m+n}$.
\st[퀗������ ���������.] 󑒀������ $i\asg 1$, $j\asg 1$, $k\asg 1$.
\st[퀉�� ���������� �������.] 呋� $x_i\le y_j$, �� ������� � 
����~\stp{3}; � ��������� ������ ������� �~\stp{5}.
%%194
\st[⛂���� $x_i$.] 󑒀������ $z_k\asg x_i$,  $k\asg k+1$,  $i\asg i+1$. 
呋�~$i\le m$, �� ������������ � \stp{2}.

\st[⛂���� $y_j, \dots, y_n$.] 󑒀������ 
$(z_k, \ldots, z_{m+n})\asg(y_j, \ldots, y_n)$ � ��������� ������ ���������.

\st[⛂���� $y_j$.] 󑒀������ $z_k\asg y_j$, $k\asg k+1$, $j\asg j+1$.  
呋� $j\le n$, �� ������������ � \stp{2}.
\st[⛂���� $x_i$, \dots, $x_m$.] 󑒀������ 
$(z_k, \ldots, z_{m+n})\asg(x_i, \ldots, x_m)$ � ��������� ������ ���������.
\algend
\picture{���. 29. 񋈟��� $x_1\le \ldots\le x_m$ � $y_1\le\ldots\le y_n$.}

� �.~5.3.2 �� ������, ��� ��� ������� ���������, �� ��������, "��������� 
�� ���������" �������� ������� �� ������������ ���, ���� $m\approx n$. 
(�, ���� $m$ ������� ������ $n$, ����� ����������� ����� ����������� 
��������� ����������, ���� � ����� ������ ��� �������� ������.) ��������~M 
��� ������ ������ ������������� ����� ������� ���������, ������� � 
����� �������� ������ ������������� "�������" $x_{m+1}=y_{n+1}=\infty$ 
� �������������� ����� �������~$\infty$. ������ ���������~M ��. � ���.~2.

�� ����� ������, ����������� ����������~M, �� ��������, 
�������������� $m+n$, ������� ����, ��� �������---����� ������� ������, ��� 
����������. ��� ������ ���������� ����� ������ � ��������, ������ ��� 
����� ������� �������� �� ��� ���, ���� �� ����� ������������ ���� ����. 
򀊎� ������ ����� ������������� ��� �������� ���� ���������� ���������: 
������� ������ �������� � ������������� ����---������� ������ ������� ��� 
$n=1!$ 呋� ����� �������� ������� �������, �� ����� ����������� ������� 
���������� ��������� �� ���, "���������" ��, � ��� ������������ ������� 
�������� � ����� ���� ���������� ��������. � ������������ ����� ������ 
����� �������--- ���� �� ����� ������ �������, ��������������� ��� ����������
%% 195
\picture{򀁋��� 1 񎐒������ ������������ ����������� ��������}
�� ���; �� ��� ��������� 䆎��� ��� 텉����� ��� � 1945~�. (��. \S~5.5).

� �������� �������� ������ ������� � \S~5.4 � ����� � ����������� ������� 
����������, � � ��������� ������ ������������ ���� �������� �� 
���������� � ������� ������ � ������������ ��������.

򀁋���~1 ������������ ���������� ��������, ����� "������ ��������� � 
����� ������", ������� ��� ���������� ��������� ��������� �����, ������� 
����������� ��� ������� ����������, ����������� �������� ���������� �~�.~�.
 � ����������� �������� ���� ����� � ������, �������� � ��������. 
������ ���� ������ ������ � ���������� ������� �� ������ ������ � 
�������. 񋅂� �� ����� ������������ ������� $503$ $703$ $765$, � ������, 
���� ������ ������ ������, ����� ������� $087$ $512$ $677$. 񋈟��� ���� 
���� ������������������� ���� ������� $087$ $503$ $512$ $677$ $703$ $765$, 
������� ���������� ����� � ������~3. 瀒�� ����� $061$ $612$ $908$ � 
������~2 ��������� �~$170$ $509$ $897$, � ��������� $(061$ $170$ $509$ 
$612$ $897$ $908)$ ������������ \emph{������} � ������~3. 퀊����, $154$ 
$275$ $426$ $653$ ��������� � $653$ (���������� �������������� ������, 
��� ��� ����� �������� � ������� ������������), � ��������� ������������ 
�����. 򎗍� ��� �� ������~2 ���������� �� ��������� ����� � ������~1.
 
⅐���������� ������� � ����.~1 �������� ������� ����� ���������. ��� ��� 
���������� "��������� ����", ��� ������� ������� ������� �� �������. � 
�������� ����� ������ ��������� ������������� ��������, ����� ��� �������� 
� ����� ������ �� ����������� ���� � ��� �� ����; ��� �� �������� � 
�����������, ���� �������� ������� ������������, ��� � 
��������� ���������. 򀊎� ����� �� �������� ���������� 
"������������" ��������, ������ ��� �� ���������� �������, ������� 
"�����������" ���������� � �������� �����.

\alg N.(񎐒������ ������������ ����������� ��������.)  ���������� 
������� $R_1$, \dots, $R_N$ ������������ ��� ������� ������, ������ �� 
������� ����� ��������� $N$~�������. 䋟 �������� ��������� ������, 
����������� �� ������ �������,
%%196
����� $R_{N+1}$, \dots, $R_{2N}$, ���� � ���������������� ������~$R_{N+1}$ 
����� � �� ��������� ��������������� �~$R_N$. 퀗������ ���������� ������� 
$R_{N+1}$, \dots, $R_{2N}$ �� ����� ��������. �� ���������� ���������� 
����� ����� �����������: $K_1\le\ldots\le K_N$.
\picture{���. 30.  񎐒������ ��������.}

\st[퀗������ ���������.] 󑒀������ $s\asg0$. ( $s=0$ �� ����� 
���������� ������ �� ������� $(R_1, \ldots, R_N)$ � ������� $(R_{N+1}, 
\ldots, R_{2N})$; ��� $s=1$ ������� �� ��������� � ���������� ���������� ������.)

\st[������� � ���������.] 呋� $s=0$, �� ���������� $i\asg1$, 
$j\asg N$, $k\asg N+1$, $l\asg2N$; ���� $s=1$, �� ���������� $i\asg N+1$, 
$j\asg2N$, $k\asg1$, $l\asg N$. (������� $i$, $j$, $k$, $l$ ��������� 
������� ������� �� ������� "������", ������ ���� ������, � � �������� 
"������", ���� ���� ������.) 󑒀������ $d\asg 1$, $f\asg1$. 
(�������~$d$ ���������� ������� ����������� ������, $f$ 
��������������� ������~0, ���� ���������� ���������� ���������.)

\st[񐀂����� $K_i:K_j$] 呋� $K_i>K_j$, ������� � ����~\stp{8}. 呋� 
$i=j$, ���������� $P_k\asg R_i$ � ������� � ���� \stp{13}.

\st[������ $R_i$.] (���� \stp{4}--\stp{7} ���������� ����� 
M3--M4 ���������~M.) 󑒀������ $R_k\asg R_i$, $k\asg k+d$.

\st[񒓏����� ����?] 󂅋����� $i$ ��~1. 瀒��, ���� $K_{i-1}\le K_i$, 
������������ � ���� \stp{3}.
\st [������ $R_j$.] 󑒀������ $R_k\asg R_j$, 
$k\asg k+d$.
\st[񒓏����� ����?] 󌅍����� $j$ ��~1. 瀒��, ���� $K_{j+1}\le K_j$, 
������������ � ���� \stp{6}; � ��������� ������ ������� � ���� \stp{12}.

%% 197
\st[������ $R_j$.] (���� \stp{8}--\stp{11} ����������� �� ��������� � 
�����~\stp{4}--\stp{7}.) 󑒀������ $R_k\asg R_j$, $k\asg k+d$.

\st[񒓏����� ����?] 󌅍����� $j$ �� 1. 瀒��, ���� 
$K_{j+1}\le K_j$, ������������ � ���� \stp{3}.

\st[������ $R_i$.] 󑒀������~$R_k\asg R_i$, $k\asg k+d$.

\st[񒓏����� ����?] 󂅋����� $i$ ��~$1$. 瀒��, ���� 
$K_{i-1}\le K_i$, ������������ � ���� \stp{10}.

\st[��������� �����������.] 󑒀������ $f\asg0$, $d\asg-d$ � 
�������������� $k\xchg l$. ⎇��������� � ���� \stp{3}.

\st[��������� ��������.] 呋� $f=0$, �� ���������� $s\asg 1-s$ � 
������������ �~\stp{2}. � ��������� ������ ���������� ���������; ���� 
$s=0$, �� ���������� 
$(R_1,~\ldots, R_N)\asg(R_{N+1}, \ldots, R_{2N})$. (呋� ��������� ����� 
�������� � �������~$(R_{N+1}, \ldots, R_{2N})$,  �� ��������� ����������� �������������.)
\algend

� ���� ��������� ���� ���� ��������� ��������, ������� ����������� � ���.~5.

瀏�������������� ��������~N ��� ������~\MIX\ ��������, �� �������� 
�������� � ��� ��������� ����� �������� � ��� ���������� ���� ���������. 
呋� ���� �������, �� � ��� �����
${1\over2}N$ ������������ ��������, ��� ��� $K_i>K_{i+1}$ � 
������������~$1\over2$; ��������� ���������� � ����� �������� ��� 
��������� �������� �������������� ���� �������� � �.~5.1.3.  ������ 
��������� ����� �������� ����������� ����� (�� ����������� ��������� 
�������, �����, ��� ��������, ��������� � ���.~6). 򀊈� �������, ����� 
����������, ��� �������, ���������� �����~$\log_2 N$.  ������ ��������� 
�� ������ ���������� ��� $N$~�������, �, ��� �������� � ���.~2, �\'������ 
����� ������� ������������� � �����~N3, N4, N5, N8, 
N9. 呋� �������, ��� ������ ����� ����������� � ����� ������������, 
�� �����, ������������� �� ���������� �����, ����� 
���������������� ��������� �������:
\ctable{
\hfill# & # & #\cr
\hbox{���}\hfill&\hfill\hbox{�����}\hfill&\hfill\hbox{␅��}\hfill\cr
$\matrix{N3\cr}$ & $\matrix{|CMPA|, |JG|, |JE|\cr}$ & $\matrix{3.5u}$ \cr
$\hbox{눁�}\left\{
\matrix{
N4\cr
N5\cr
}\right.$
& 
$
\matrix{
|STA|, |INC| \hfill\cr
|INC|, |LDA|, |CMPA|, |JGE|\hfill \cr
}
$
&
$\matrix{
\phantom{0.}3u\cr
\phantom{0.}6u\cr
}$
\cr 
$\hbox{눁�}\left\{
\matrix{
N8 \cr
N9 \cr
}\right.$
&
$\matrix{
|STX|, |INC|\hfill \cr
|DEC|, |LDX|, |CMPX|, |JGE|\hfill\cr
}$
&
$\matrix{
\phantom{0.}3u\cr
\phantom{0.}6u\cr
}$
\cr
}
򀊈� �������, ��� ������ ��������� �� ������ ������ ������������� 
$12.5$~������ �������, � ����� ����� ������ �������������� ������������ 
�~$12.5N\log_2 N$ ��� � �������, ��� � � ��������� ������. ��� ��������� 
������� ���������� � �� ��������� ����� ������� ������ ������������� 
����������, ����� ��������� ����� ������� ������ ������, ��� ��� 
��������������� ����� ������ ���������~5.2.3H ����� $16N\log_2 N$.

%% 198

� ���������~N ������� ����� ��������� ��������� ������������ 
"����������� ����". 򀊎� ������ �������� ��� ��������� �������������, 
��� �������� ����� � ������������� ������������� \emph{��� ����������} 
������������ ��������� ����� �������������� ����� ������, �� ��� ���� 
����������� �������� ���� ����������. ⌅��� �������� �������� ���� ����� 
������������� ���������� ����� ��������, ������, ��� ��� 
������� ��������� ����� ����� �����~$1$, ����� ������� ��������� 
��� ������� (�����, ��������, ����������) ����� ����� 2, \dots, 
����� $k\hbox{-�o}$ ��������� ��� ������� (�����, ��������, 
����������) ����� �����~$2^k$. � ������� �� "�������������" ������� � 
���������~N ����� ������ ���������� \emph{�������} ����������� ��������.

�������� �������� ������������ ������� ����� ���������� ��������~N---�� 
�����������, �� ��������, ��� �� ����-������;
��� �� ����� ������ ���������� ���������� ���� �� �����, � ������� ����� 
�������� ���� �������� �������.

\alg S.(񎐒������ ������� ����������� ��������.) ꀊ � � ���������~N, ��� 
���������� ������� $R_1$, \dots, $R_N$ ������������ ��� ������� ������.

\st[퀗������ ���������.] 󑒀������ $s\asg0$, $p\asg1$. 
(񌛑� ����������~$s$, $i$, $j$, $k$, $l$, $d$ ��. � ���������~N. 焅�� 
$p$---������ ������������ ��������, ������� ����� ��������� �� ����� 
�������� ���������; $q$ �~$r$---���������� �������� ��������� � ��������.)

\st[������� � ���������.] 呋� $s=0$, �� ���������� $i\asg1$, 
$j\asg N$, $k\asg N$, $l\asg2N+1$; ���� $s=1$, �� ���������� $i\asg N+1$, 
$j\asg2N$, $k\asg0$, $l\asg N+1$. 瀒�� ���������� $d\asg1$, $q\asg p$, 
$r\asg p$.

\st[񐀂����� $K_i:K_j$.] 呋� $K_i>K_j$, �� ������� � ����~\stp{8}.

\st[������ $R_i$] 󑒀������ $k\asg k+d$, $R_k\asg R_i$.

\st[ꎍ�� �������?] 󑒀������ $i\asg i+1$, $q\asg q-1$. 呋� $q > 0$, �� 
������������ � ����~\stp{3}.

\st[������ $R_j$.] 󑒀������ $k\asg k+d$. 瀒��, ���� $k=l$, ������� � 
����~\stp{13}; � ��������� ������ ����������
$R_k\asg R_j$.

\st[ꎍ�� �������?] 󑒀������ $j\asg j-1$, $r\asg r-1$. 
呋�~$r>0$, ������������ � ���� \stp{6}; � ��������� ������ �������
� ���� \stp{12}.

\st [������ $R_j$.] 󑒀������ $k\asg k+d$, $R_k\asg R_j$ 

\st[ꎍ�� �������?] 󑒀������ $j\asg j-1$, $r\asg r-1$. 
呋�~$r> 0$, �� ������������ � ����~\stp{3}. 
\st[������ $R_i$.] 󑒀������ $k\asg k+d$. 瀒��, ���� $k=l$,
������� � ����~\stp{13}; � ��������� ������ ����������
$R_k\asg R_i$.
%% 199
\st[ꎍ�� �������?] 󑒀������ $i\asg i+1$, $q\asg q-1$. 呋� $q > 0$, �� 
������������ � ���� \stp{10}.

\st[��������� �����������.] 󑒀������ $q\asg p$, $r\asg p$, $d\asg -d$ 
� �������������� $k\xchg l$. ⎇��������� � ���� \stp{3}.

\st[��������� ��������.] 󑒀������ $p\asg p+p$. 呋� $p<N$, �� 
���������� $s\asg 1-s$ � ������������ �~\stp{2}. � ��������� ������ 
���������� ���������; ���� $s=0$, �� ����������
$$
(R_1, \ldots, R_n)\asg (R_{N+1}, \ldots, R_{2N}).
$$
(텇������� �� ������������� ��������� ����� ��������� ����������� ����� 
��������� ����� � ������ �����, ����� ��������~$\ceil{\log_2 N}$ �������. 
� ��� ����� ������� ����������� ��������� ���������������� �����, � 
�����������, ��� �������, �� ���������.)
\algend

{\def|{\mskip\thinmuskip\vert\hidewidth}
 \catcode`\!=\active
 \def!{\mskip\thinmuskip\vrule width 0.5mm\hidewidth}
\htable{򀁋��� 2}%
{񎐒������ ������� ����������� ��������}
{\bskip$#$\bskip&&\bskip$#$\bskip\cr
503|& 087|& 512|& 061|& 908|& 170|& 897|& 275!& 653|& 426|& 154|& 509|& 612|& 677|& 765|& 703\cr
503 & 703|& 512 & 677|& 509 & 908|& 426 & 897!& 653 & 275 & 170 & 154|& 612 & 061|& 765 & 087\cr
087 & 503 & 703 & 765|& 154 & 170 & 509 & 908!& 897 & 653 & 426 & 275|& 677 & 612 & 512 & 061\cr
061 & 087 & 503 & 512 & 612 & 677 & 703 & 765!& 908 & 897 & 653 & 509 & 426 & 275 & 170 & 154\cr
061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908\cr
}
}

��� ������ ��������� ��. � ����.~2. 䎂����� �����������, ��� ���� 
����� ���������� � �����, ����� $N$ �� �������� ��������~2; ��������� 
������� �� ��� ����� ����� $2^k$, ��� �� ����� ������� ����� ��� 
���������������� �� ������ ����� ���������� �� �������������! (�. 
���.~8.) ����� �������� ���� �������� ����������� ����������~$q$ �~$r$ 
� ��������� �� ��������� ����. ዀ������ ����� ����� ������ �� ������ 
\MIX\ �������������� ������������ � $11N\log_2 N$~��������, ��� ��������� 
����� ��������, �������� ��� ������� �������� � ���������~N.

� �������� ����� ����� ������������� ��������~S � �������� ���������; 
������ ������ ������� ���������� ���������~S ����� �������� ��������� 
������������� ������, ������, �� 16~���������, �������� ����� ������� 
�������� �������������� ��������������� ��������, ��������� �� �������� 
�������� ������. ꀊ �� ��� ������ � ������ ������� ����������, 
����� �������������� ������� �� ������/�� ��������������� ����� ������, �� 
���� ��� �� �����, ������� ������.

���������� ������ ���������~N �~S � ����� ������ �������� ������. ��� 
��� ���������� ������ ��� $2N$, � �� ��� $N$
%% 200
~�������? ���� ������������ ������: �� �������� � �������� �������� 
����������� ������� (��� "������� ������" � ��� "�������� ������" � ������ 
���������); ��� ���� ��� ������ ���� ��������������� �������������� 
������� �� ���������� ����������� �������� "���������� �����", 
������������� � (�.~2.2.2. � � ����� ������ ������� �������� ������ �� 
������������, � ����� ���������� ����������� ���������� ����, ��� � 
����������������, ��� ����� ������� ������� ��������� �� ��������������� 
\emph{���������} �������������� ������. 呋� � ������ �� $N$~������� 
�������� ���� �����, �� ��� ����������� ����� ���������, ��������� 
����������� �������, ������� ���������� ������� ����������� �� ������� � 
������ �� ���������� ���� ������. 䎁������� $N$~����� �����, ��� 
�������, ��������, ��� ���������� ������������ ������ ��� ��� 
$N$~�������, � ����������� �� ����������� �������, �� ����� 
����� ���������� � �����. 蒀�, ��� ����� ����������� ��������, �������� 
����������.

\alg L.(񎐒������ ����������� ������� �������.) �����������, ��� 
������ $R_1$, \dots, $R_N$ �������� ����� $K_1$,~\dots, $K_N$ � "���� 
�����" $L_1$,~\dots, $L_N$, � ������� ����� ��������� ����� ��~$-(N+1)$ 
��~$(N+1)$. � ������ � � ����� ����� ������� ������������� ������~$R_0$ 
�~$R_{N+1}$ � ������ �����~$L_0$ �~$L_{N+1}$ ���� �������� ���������� 
������� ������������� ���� ����� ����� �������, ��� ������ ����������� 
���������� � ������������ �������. �� ���������� ���������� $L_0$ 
��������� �� ������ � ���������� ������; ��� $1\le k \le N$ �����~$L_k$ 
��������� �� ������, ��������� ��~$R_k$, � ���� $R_k$---������ � 
���������� ������, �� $L_k=0$. (�. ������� (5.2.1--9).)

� �������� ���������� ����� ��������� ������~$R_0$ �~$R_{N+1}$ ������ 
"��������" ���� �������� �������, ��������� ������� � ������ ������ 
���������. ���������� ����� �������� ����� ���������, � ������� 
��������, ��� �� ����������; ������� ����� �������� ����� ����� ������. 
�����������, ��� $N\ge 2$.

����� "$\abs{L_s}\asg p$" ���������� �������� "��������� $L_s$ 
��������~$p$ ���~$-p$, �������� ������� ���� $L_s$". 򀊀� 
�������� ����� ����������� �� ������ \MIX, ��, � ���������, ��� �� ��� ��� 
����������� ���. 텒����� �������� ��������, ����� �������� ����� �� 
����������� ����� � ��� ����������� ������ �����.

\st[�������� ��� ������.] 󑒀������ $L_0\asg1$, $L_{N+1}\asg2$,
 $L_i\asg -(i+2)$ ���~$l\le i\le N-2$ �~$L_{N-1}\asg L_N\asg0$. (� 
������� ��� ������, ���������� �������������� ������~$R_1$, $R_3$, $R_5$,
~\dots{} �~$R_2$, $R_4$, $R_6$,~\dots{}; ������������� ����� ������� � ���,
 ��� ������ ������������� "���������" ������� ����� ���� �� ������ 
��������. 䐓��� ������ ��������� ���� ���,
%% 201



\bye