\input style

���� �������� ����� �� ������ ��� ������� ����� ����������, �� � ������, 
��� �� ����� ����������� ��� ����� ������ ���������� ��������� �������. � 
����.~8 �������� ������ ��������� ����� ���������� ����������� �����, 
��������� ���� ��� ��������.

\prog L.(⑒���� � ������.) �����������, ��� ����~$K_j$ �������� � 
����~$|INPUT|+j(0:3)$,  a~$L_j$---� ����~$|INPUT|+j(4:5)$. 獀����� 
���������: $|rI1|\equiv j$; $|rI2|\equiv p$; $|rI3|\equiv =q$; 
$|rA|(0:3)\equiv K$. 
\code
KEY  &EQU  & 0:3
LINK &EQU  & 4:5
START&ENT1 & N            & 1      & L1. ���� ��~$j$, $j\asg N$.
     &ST1  & INPUT(LINK)  & 1      & $L_0\asg N$.
     &STZ  & INPUT+N(LINK)& 1      & $L_N\asg 0$.
     &JMP  & 6F           & 1      & ���� � ����������~$j$.
2H   &LD2  & INPUT(LINK)  & N-1    & L2. 󑒀������~$p$, $q$, $K$. $p\asg L_0$.
     &ENT3 & 0            & N-1    & $q\asg 0$.
     &LDA  & INPUT,1      & N-1    & $K\asg K_j$.
3H   &CMPA & INPUT,2(KEY) & B+N-1-A& L3. 񐀂����~$K$, $K_p$.
     &JLE  & 5F           & B+N-1-A& K~L5, ����~$K\le K_p$.
4H   &ENT3 & 0,2          & B      & L4. �������~$p$, $q$. $q\asg p$. 
     &LD2  & INPUT,3(LINK)& B      & $p\asg L_q$.
     &J2P  & 3�           & B      & � L3, ����~$p>0$.
5H   &ST1  & INPUT,3(LINK)& N-1    & L5. ⑒����� � ������. $L_q\asg j$.
     &ST2  & INPUT,1(LINK)& N-1    & $L_j\asg p$.
6H   &DEC1 & 1            & N
     &J1P  & 2�           & N      & $N>j \ge 1$.
\endcode
\progend

␅�� ������ ���� ��������� ����� $7B+14N-3A-6$~������, ���~$N$---����� 
�����, $A$---����� �������������� ����������, �~$B$---����� �������� � 
�������� ������������. (�. � �������� ���������~S. 瀌�����, ��� 
���������~L �� ���������� ������ � ������; ��� ����� �������, ��� � 
���.~5.2-12, �������� ������������� $20N$~������ �������.) ������~S 
������� $(9B+10N-3A-9)u$, � ��� ��� $B$~����� ��������~${1\over 4}N^2$, ��
�������� ������, ��� �� ���� ��������������� ������������ ������, 
����������� ��� ���� �����, ������� ���������� �������� 22\% ������� 
������. ��������� ������������, ����� ������� ��� 22\% (��.~���.~33), �� 
����� ������ ��� �� ��������� ����������������~$N^2$.

\emph{����� ���� ���������� �� ��� ���.} � ������ � 
���������~S---�������� � ������������� ��������� ����������, �������
%%122
��������� ����� ${1\over4}N^2$ ��������� � ����� ${1\over4}N^2$ 
�����������. � ����������������� ���, ���������� �������� �������, ��� 
������� ����������� ����� $N\log_2N$ ��������� � ${1\over4}N^2$
�����������. 텑������ ������� ��������� ������, �������� "����������� 
�������", ������ ��������� ����� �����������
�� ${1\over8}N^2$.  ���������� ������� ����� "� ��������� �����"
����� ��������� � ����������� ��������� �������� �� $N^{1.3}$ ��� ��� 
�������� $N$, ������� ����������� �� ��������; ��� $N\to\infty$ ��� ����� 
����� ��������� �� ������� $N(\log_2N)^2$. 䀋������� ���������� �������� 
��������---����� ���������� ��������� ��������� ������---������� ��� � 
�������� � ������,
��� ������� ����������� ����� ${1\over4}N^2$ ���������, 0 �����������
� $2N$ ��������� ������.

쎆�� �� ��������� ������ �������� ���� �������, �������� ����� ��������� 
�� ������� $N\log N$, ��� ��� �������� ��������, � �������� ��� ���� 
����������� ������, ��� ��� ��������
\picture{���. 13. ��� ����� 󈋅�� ��� ������� � ������.}
� ������? �� ��������������: ��� ����������� ��������� � ����������� 
���������. 򀊀� ����������� ���� ������� ����������� ����� 1957~�. 
�.~�.~󈋅���, ������� ��������� ������������ ����������� ������� �� ��� 
���, ���� �� �������� ������������� ���������� ������. 򎃄� ������ ����, 
����� �� ����������, ����������� ��������� �� ����� ������� ������, � ��� 
�� ����� ����� ����������� ����������� �� ���� ���������, ������� ����� 
�������� � ��� ����� ������� ������. ��������� ����� 󈋅�� 
[��. A. S. Douglas, {\sl Comp. J.,\/} {\bf 2} (1959), 5] ������������ 
����� ������� ���������� ���������������� � ��������� ������ � ������ 
����������� �������; ��� ����� ����������� ����� ���� �� ������������ 
������, ���������� �� ���.~13. �����������, �� ����� ������� ����� 
������� � ������ � �������������� �������� �������� ���������� 
%% 123
���������� ����� 1958~�. �.�.~ᅐ���-� 
[��. {\sl Comp. J.\/}, {\bf 3} (1960), 174, 184]. 
� ���� ����� � ��� ������������ ������ ����� ��� ��� ����������, ��� � 
��� ������, ������� �������� ��� ����������� � ��.~ 6.

噅 ���� ���� �������� ������� �������---���������� ��������� ��������� 
��������� ������������. 呋�, ��������, ������� ���� �� 1000 ��������� � 
998 �� ��� ��� �������������, �� �������� S �������� ��� ��� ��������� 
����� (������� ������� $R_{999}$, � ����� $R_{1000}$). �����, ����� 
���������� �����, ���� ������� �������� ����� $K_{999}$ c $K_{1000}$ ����� 
��������, ������� �� ��� ������, � ����� �������� �� \emph{���} �� ���� 
�������� �����. ꎌ������������ �������� ������ ���� ������� ����� 
$(2/3)N$ ��������� � ����������� (��. � ���.~3.4.2--5) ������ ���� 
����������, �������� �� $N/2$ ��������� � ����������� ������.

荀�� ������, ������ ������ ������� "������������" ��������, ������� 
������� ����������� ������, ����� ����� ���� ��������� ��������� �������� 
������. 呋� ������� ��� ���� �� �� ������������� ����������, �� �� ������ 
������� ��� ���� ���������� ����������� �������, ��������� ������, ��� 
�� �������� ��������� �����.

\section 񎐒������ � ����������� ������. 򅏅�� �� ��, ����������,
 ��������� ��� ��������� ������� ����������������� ����� ������� �������, 
�� ������� �������� ���! �������� ����, ��� ��� ���� ������ ���� ������ 
� ���������� ��������� �����-�� �����. ‘� ������---�������� �� � 
���������� ������� � ������� ������ � ��������������� ������� ����. 
󑋛��� ����� �� ����� �, �� ������ ���������� �������� ��� ����� � 
�������� ���� ��������, ����� ��� ����� �� ����� � �����, ��-��������, 
�������� ����� � ������� ���� �������� �~�.~�. ����������� ������ 
����������� ��� ����������� ���� �� ����� �� �������� �������, ���� ����� 
������� � ���� � ��������� �������: ����� ����� �� �����, �� ���������� �� 
�������� ���������, �������� ����� ������� ����� ����������� ��������� � 
�����������. (������������� �������� ����������, ���� �� ����� ������� 
������� ������ �����, ��� ��� ��������� ����������.) 򀊎� ����� �������� 
���������� ������� ���������� 葀�� � 񈍃����, 
[{\sl JACM\/},  {\bf 3} (1956), 169--174];
�� ������� ���������� �������� � ������ ꐎ����� � 򀐒��� 
[Proc. ACM Nat'l Conf., {\bf 21} (1966), 331--337].

񎐒������ � ����������� ������ ������ ������� ��������������� 
������������ ������ ���� ��� ����, ����� �������� ���������� ���������� 
����� � �� ������ ����� ������ �����������, ���� ��� �������� 
��������������� ������, ������� �� ��������� ��������� ��������������� 
������������� ������. (�.\ ���������� �������������� ��������� (��������~5.2D),
%% 124
\bye
