\input style
\chapnotrue
\chapno=5
\subchno=1
%% 93
\subchap{���������� ����������}
������ ���������� �������� "������������" � ���������� ������������: ��� 
�� �� ������ ��������� ������ ����������������?                    $$
\vtop{
\narrower
"��� ������ $|R|+1$,  $|R|+2$, $|R|+3$, $|R|+4$ �~$|R|+5$
�������� ���� �����. �������� ���������, ������� �������������, ���� �����,
 ��� ����� ���, ����� ��� ������������� � ������������ �������."
\par
}
$$
(���� �� ��� ������� � ������-���� �������� ����������, ������������, 
����������, �� ������ ������ � ���; ����������, ��� �� ������� ����� 
������ �������, �� ���� ������� ��������������� ������ � ���, ��� � ��� ������������.)

\bigskip
\emph{
������ ��� ������ ������, ������������ ������ ��� ����� ���� �����-������ 
������� ���� ������.
}
\bigskip
\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}
\bigskip

�����, ����������� �� ������� ����������� ���� ������, �������� � ������, 
����� �� ���������� ������ ���� �����. ��������, ���� ������� �������� 
����� �� ���������:

\medskip
A.{\sl  ᎐������� ���������.\/} 틅����� ��������������� �� ������, � 
������ ����� ������� ����������� � ���������� ����� ����� ����� 
������������� ���������. (������ ����� �������� ������ � ����� 
������������� ���� �����, ���� �� �����.)

B.{\sl  �������� ����������.\/} ���� ��� �������� ����������� �� �� 
�������, �� ��� �������� �������. 풎� ������� ����������� �� ��� ���, 
���� �������� �� ����� �����������.
 C. {\sl ᎐������� ����������� ������.\/} ፀ���� ���������� 
���������� (���. ���� �����, ����������) ������� � �����-���� ������� 
���������� �� ���������, ����� ���������� ���������� (����������) �� 
���������� � �. �.

D. {\sl ᎐������� ���������.\/} ������ ������� ������������ �� ����� 
����������; �������������-��������� �������� ������������ ��������� 
����� ������� ������.

E. {\sl Ꮕ�������� ����������\/}, ������� ������ ��� ���� ���������, 
��������� � ������, �� �� ��������� �������� ��������� ��. ������ 
�������� ����� ���������.
%% 94
F. {\sl ������� �������.\/} �� �� ������������ �� ���� ����������� � 
���������� ������ ������. ����, �� ������, ����� �� ������ ��� �����, ��� 
���� ������.

G. {\sl ����� ���������������\/}, ������� ������������ ����� 
������������ ������������������ ��������� �������. (����������,
 ���������� �������� �� ���� ������.)
\medskip

���� �� ��� ������ ���� ��������������, ������, ��� 1000 ���������, � �� 
��� 5, �� �� ����� �� ������� � ��������� ����� ������ ������, � ������� 
����� ��������� ����. � ����� ������, ��������� � ����� ������, ������� 
����� �����-������ ��������� ���������, � ����� ���������� �������� 
��. ዓ��� �, � � � �������� � ������ ������� ������� ����������, 
������� ������������ ����� ������������������ ���������������� ���� 
������� ����.

���� ���������� ��������� ��������� ���������� ����������, � � ���� 
����� ��������������� ����� 25 �� ���. 풎 �������� ���������� ������� �� 
����� ���� ���� ����� ������ ���� ����������, ����������� �� ��� ���; 
������, ��� ���������� ������ �� ����� �� ����� ������������� ��� 
�������� ���� ��������. ������ �� ��� ����� ������� ����������? 
��� ���������������� ��� ������� ������ �������: "������ ���������� ��� 
����� ������� $x$?", ��� $x$ ��������� ��������� ���� �����. ����� ������� 
� ���, ��� ������ ����� ����� ���� ������������ � ����������, ������� �� 
����������� ����������� ������ ��� ��������� ������������� ������ � 
����������. � ���������, ���������� "���������" ������ ����������;
���������� \emph{�����} ��������� ������� � ����������� �� ����, ��� 
�����������, �� ����� ������, ��� ����� ����. ������ ������� �������� 
��������, "���������� 9 � ��� 60 �������� ������� ����� �������, � ������ 
�� ��� � ����������� �����".

������� ������� �������������� ������� ������ ����������, ����� ����� ���� 
����������� �������� ����� ��� ���������� ����������. � �������, ������ 
�������� ���� ���������� �� ����� �� ���������, ��������� ����� ���� 
���������� ���������� �����������.

� ������ ���� ����� �� ����� �������� ������������ � �����������, ������� 
� ����� ������������ ��� �������� ����������. ������
$$
R_1, R_2, \ldots, R_N
\eqno(1)
$$
������ ���� ������������� � ����������� ������� �� ����� ������ $K_1$, 
$K_2$, \dots, $K_N$, �� ��������, ����� ���������� ������������ $p(1)$ 
$p(2)$ \dots $p(N)$,  �����, ���
$$
K_{p(1)}\le K_{p(2)}\le \ldots \le K_{p(N)}.
\eqno(2)
$$
%% 95
� ���� ��������� ��������������� \dfn{���������� ����������}, ����� ����� 
�������, ���������� ����������, ���������� ����, ��� ��� ���� ������� 
����� �������� � ����������� ������ ���.

� ����� ������� ����� ������������ ��������� �������������� ������ � 
������ ���, ����� �� ����� ���� �����������;
� ������ ����� �������� ��������������� �������� ����������
\picture{���. 6. ᎐������� ������� �������.}
����, ������� ���������� ������������. ���� ������ �/��� ����� �������� 
��������� ���� ������, �� ����� ����� ��������� ����� ������� ������� 
(������), ������� ��������� �� ������, � �������� � ����� ��������, �� 
��������� ���������� ������.  �� ����� ���������� \dfn{����������� 
������� �������}
\picture{���. 7.  ᎐������� ������.}
(���~ 6.). ���� ����� ��������, � ������������� ���������� � ������� 
������, �� ��� ��������� �������� ����� ����� ������� � ������� �������; 
��� ���������� \dfn{����������� ������}. ������ ����� ���������� 
���������� ��������������� ���� �����, ������� ���������� � ������ ������. 
႟�� �������������� ����� �������, ��� � ���������� ��� ������ 
����������� ���������� � �������� ������, � ������� ������ ����� 
��������� �� ��������� �� ������� ������. 풎 ���������� 
\dfn{����������� ������} (���. 7).

%% 96

����� ���������� ������� ������� ��� ���������� ������ ����� �� ������� 
����������� ������ � ����������� �������. ��� ����� ������� ��������� 
��������, ��������� �������������� ������ ��� �������� ����� ����� ������ 
(��. ���. � 10 �� 12);
��� �� ����� ������ ����������� ������ � ����� ������� ������,  ���� ��� 
����� �������� ��� ��� ������. ��������� ������ ������ ����� ������� 
�������, �� ������� ����� � ��� ���� ������ ������. �� ������ ����������� 
����� �� ����������� ���������� ������, ��� ��� ���� �����, ��� �������, 
������ ��������� ��� �������� � ���������������� ����������.

��� ������ ����������, ������� �� ��������� "�����������", ����� 
����������������� �������� ���������: �����������
\medskip
\item{a)} ���������� �������� ���������,
\item{b)} ����-�����,
\item{c)} ��������� ��� ������ \MIX,
\item{d)} ������� ���������� ����� ������ ���������� � ��������� ��������� �����.
\medskip
[� ��� ��������, ��� ��� �������, ����� �������������� ��������� �� 16 
�����, ������� �����, ��������� ������� ���������� ��������� ������, 
������ ��������� ������� 19 ����� 1963 �.; ��. � ���. 3.1--1 (�).]

�� ����������� �������� ��������� ��� ������ \MIX\ �����, ��� �������, 
�������� � �������������, ��� ���� �������� � ��� �� ���������� � ����� 
�����; ������ �� ���� ����� ������������ �������� ������ ���, ����� ��� 
�������� ���� ����� �����. ���������� ������� $<$ ����� ������� 
�������������� ��������� �������, � ������ ����� �������� �� ������ 
�����, ��� ������������� ����������. � ���� �������������� 
��������� ���������� ������, ����� ��� ���������, � �� ������������ ����� 
�������������� �� �� ����� ������ (��������, �������� ���������� ������ 
�������). ������ � \MIX-����������� ���������� ������ ������� ���������� 
���������������� ��������� ����������.

\section ᎐������� ���������. 璎�� ����������������� ������, ������� 
�� ����� ������� ������ ���������� ����������, ���������� ���� 
"��������", ���������� � ������ ����� ���������. 풎� ������� ����� 
������� �� ���, ��� $j$-� ���� � ������������ ������������� 
������������������ ��������� ����� $(j-1)$ �� ��������� ������. ����� 
������, ���� ��������, ��� ��������� ���� ��������� ����� 27 ������, �� 
����� ���������� ��������������� ������ ������ ������ 28-� �����.  �� 
�������, ���� ������� � ���, ����� �������� ������� ��� ����� � 
����������, ������� �� ��� ������ ������� ���������� �����.

%% 97

��������� ������ ��������� ���������---
$$
\hfill
\hbox{((�������� $K_j$ c $K_i$) ��� $1\le j \le N$) ��� $1\le i\le N$,}
\hfill
$$
�� ����� ������, ��� ����� �������� ���� �������� �������, ��������� �� 
����� ���������� ���� ��� � ����� � ����� ��������� $K_a$ � $K_b$ ��� �� 
���� ���������� $K_b$ � $K_a$. ������� ����������
$$
\hfill
\hbox{((�������� $K_j$ � $K_i$) ��� $1\le j\le i$) ��� $1 < i \le N$.}
\hfill
$$
����, �������� � ���������� ���������.

\alg �.(᐀������ � �������.) 풎� �������� ��������� ������ 
$R_1$,~\dots, $R_N$ �� ������ $K_1$,~\dots, $K_N$, ��������� ��� 
�������� ����� ������, ������� �������, ��������������� ������� 
$|COUNT|[1]$,~\dots, $|COUNT|[N]$. ����� ���������� ��������� �������� 
$|COUNT|[j]+1$ ���������� ������������� ��������� ������ $R_j$.

\st[ၐ����� ��������.] 㑒������� $|COUNT|[1]$,~\dots, $|COUNT|[N]$
������� ����.

\st[戊� �� $i$.] ��������� ��� \stp{�} ��� $i=N$, $N-1$, \dots, 2;
����� ��������� ������ ���������.

\st[戊� �� $j$.] ��������� ��� \stp{4} ��� $j=i -1$, $i-2$, \dots, 1.

\st[᐀����� $K_i$, $K_j$.] ���� $K_i<K_j$, �� ��������� $|COUNT|[j]$ �� 
1; � ��������� ������ ��������� $|COUNT|[i]$ ��~1.
\algend

�������, ��� � ���� ��������� ������ �� ������������. �� ���������� 
���������� ������� �������, ��������� ������� |COUNT| ���������� �������� 
������������ �������; �� ���
������ ��������� �����������, ������ ��� $|COUNT|[j]$ ��������� �� �����, 
���� ����� ��������� ������ $R_j$, � �� �� ������, ������� ���� ��������� 
�� ����� $R_j$. ( �� �������, ������� |COUNT| ���������� ������������, 
�������� $p(1)$~\dots $p(n)$; ��. �.~5.1.1.)

� �����������, �������������� ����� ���������, �� �� ���������, ��� ����� 
����� ���� �������. 풎, ������ ������, ��������� ��������, ������ ��� 
���� �� ������ ������ ��������������� ������ ��������, �� �������������� 
����������� ������� ���� �� �������� �������. � �������, ��� �������� � 
���. 2, �������� C ���� ������ ��������� ���������� �� ����� ������ ������.
\picture{���. 8. �������� �: ��������� � �������.}

%% 98

\ctable{|COUNT|($#$):\hfill&&\bskip\hfill$#$\hfill\bskip\cr
\noalign{\rightline{ ���� 1}}
\noalign{\centerline{\bf ᎐������� ��������� (�������� �)}}
\noalign{\vskip0.5ex\hrule\vskip0.5ex}
\omit \hfill �����: \hfill
           & 503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 703\cr
\hbox{���.}&  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0 \cr
i=N        &  0  &  0  &  0  &  0  &  1  &  0  &  1  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  1  &  12\cr
i=N-1      &  0  &  0  &  0  &  0  &  2  &  0  &  2  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  13 &  12\cr
i =N-2     &  0  &  0  &  0  &  0  &  3  &  0  &  3  &  0  &  0  &  0  &  0  &  0  &  0  &  11 &  13 &  12\cr
i=N-3      &  0  &  0  &  0  &  0  &  4  &  0  &  4  &  0  &  1  &  0  &  0  &  0  &  9  &  11 &  13 &  12\cr
i=N-4      &  0  &  0  &  1  &  0  &  5  &  0  &  5  &  0  &  2  &  0  &  0  &  7  &  9  &  11 &  13 &  12\cr
i=N-5      &  1  &  0  &  2  &  0  &  6  &  1  &  6  &  1  &  3  &  1  &  2  &  7  &  9  &  11 &  13 &  12\cr
\noalign{
\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}
}
i=2        &  6  &  1  &  8  &  0  &  15 &  3  &  14 &  4  &  10 &  5  &  2  &  7  &  9  &  11 &  13 &  12\cr
\noalign{\vskip0.5ex\hrule\vskip0.5ex}
}

\prog C.(᐀������ � �������.) � ��������� ���������� ��������� C ��� 
������ \MIX\ ��������������, ��� ������ $R_j$ ��������� � ������ 
$|INPUT|+j$, a $|COUNT|[j]$---� ������ $|COUNT| +j$, ��� $1\le j\le N$; 
$|rI1|\equiv i$; $|rI2|\equiv j$; $|rA|\equiv K_i\equiv R_i$; 
$|rX|\equiv|COUNT|[i]$.
\code
START&ENT1 & N       & 1  &�1 . ၐ����� ��������.
     &STZ  & COUNT,1 & N  &$|COUNT|[i]\asg 0$.
     &DEC1 & 1       & N
     &J1P  & *-2     & N  &$N\ge i>0$.
     &ENT1 & N       & 1  &�2. 戊� �� $i$.
     &JMP  & 1F      & 1 
2�   &LDA  & INPUT,1 & N-1
     &LDX  & COUNT,1 & N-1
3H   &CMPA & INPUT,2 & A   &C4. ᐀����� $K_i$, $K_j$.
     &JGE  & 4F      & A   &�������, ���� $K_i\ge K_j$.
     &LD3  & COUNT,2 & B   &$|COUNT|[j]$
     &INC3 & 1       & B   &$+1$
     &ST3  & COUNT,2 & B   &$\to |COUNT|[j]$
     &JMP  & 5F      & B   
4H   &INCX & 1       & A-B &$|COUNT|[i]+1\to|COUNT|[i]$.
5H   &DEC2 & 1       & A   &�3.戊� �� $j$.
     &J2P  & 3B      & A
     &STX  & COUNT,1 & N-1
     &DEC1 & 1       & N-1
1�   &ENT2 & -1,1    & N   &$N\ge i>j>0$.
     &J2P  & 2B      & N
\endcode
\progend

����� ������ ���� ��������� ����� $13N+6A+5B-4$ ������, ��� $N$---����� 
�������,  $A$---����� �������� ������� 2 �������� �� $N$, �. �. 
$\perm{N}{2}=(N^2-N)/2$, � $B$--- ����� ��� ��������,
�����, ��� $j<i$, � $K_j>K_i$.  �� �������, $B$---\emph{����� ��������} 
������������ $K_1$, \dots, $K_N$; ��� �������� �������� ��������������� 
� �.~5.1.1, � ���� ������� [������� (5.1.1--12,13)], ��� ��� �������� 
������, ������������� � ��������� �������,
$$
B=\left(\min 0, \ave {(N^2-N\over 4}, \max{(N^2-N)\over 2}, 
\dev{\sqrt{N(N-1)(N+2.5)}\over 6}\right).
$$

%% 99

ዅ����������, ���������� ��������� C �������� 
��~$3N^2+10N-4$ ��~$5.5N^2+7.5N-4$ ������ �������, � ������� ����� ������ 
��������� ���������� ����� ����� ����� ���������. ��������, ��� ������ 
����.~1 ����� $N=16$, $A=120$, $B=41$, ������, ��������� C ����������� �� 
�� ����� $1129u$. ����������� ��������� $C$, ���������� ��������� ����� 
���������� ����������������, ��. � ���.~5.

��������� $N^2$, ������� ������������ ����� ������, ��������������� � 
���, ��� �������� C �� ���� ������������ ������� ����������, ����� $N$ 
������; ��� �������� ����� ������� ����� ������������� � ������ ����. 
��������� ���� ����� ������� ��������� ���� ��� ������ $(K_i, K_j)$, �� 
��� ���������� ������� ��������� ����������� �� $N^2$, ��� �� ����� �� 
������ ������ � ���� �����, ���, ��������� "����������� � �������", 
����� ������� ������� �������� ������� ������ �� $N\log N$. �������� C 
��������� ��� ��� �� ��������������, � ������� ������� ����� ���������; 
��� �������� ������ �������� ���� �����, � ������� ����� ������� ����� 
������� (� ����� �����������) ������.

ᓙ������� ������ ������������� ���������� ����������� ��������, ������� 
\emph{�������������} ������ ����� � ����� ������ �������������; ��� 
��������� � �������� � ��� ������, ����� ������� ����� ������ ������ � ��� 
��� �������� � �������� $u\le K_j\le v$, ��� �������� $(v-u)$ ��������. 
품 ������������� �������������� ������ ����������������, �� ��,����� ���� 
�� ������ ������ ���������� ���� ����; ��������, ���� ��������� ���� 
����� ���� � ������� ������ ������, � �� �� ���� ������ �������, �� ���� 
�������� �������� ���������������, � ����� ��� ������������ ������ ������� 
���� �� �����.

璎�� ������ �������, �����������, ��� ��� ����� ����� �����~1 �~100. ��� 
������ ��������� ����� ����� ����������, ������� ������� ������, ������ 
1, 2, \dots, 100, � ��� ������ ��������� ����� ��� ����������� ������ � 
��������������� ������ ������� ������. � ��������� ��������� ��� 
��� ������� ����� ��������.
\picture{���. 9. �������� D: �������������� �������.}
%% 100

\bye