\input style
%% 109
\picture{rIS. 11. sOOTVETSTVIE MEZHDU 2-UPORYADOCHENIEM I PUTYAMI NA RESHETKE. 
kURSIVOM NABRANY VESA, SOOTVETSTVUYUSHCHIE CHISLU INVERSIJ V 2-UPORYADOCHENNOJ 
PERESTANOVKE.}

pUSTX $A_n$---SUMMARNOE CHISLO INVERSIJ VO VSEH 2-UPORYADOCHENNYH 
PERESTANOVKAH MNOZHESTVA $\{1, 2, \ldots, n\}$. yaSNO, CHTO $A_1=0$, $A_2=1$, 
$A_3=2$, A IZ RASSMOTRENIYA SHESTI SLUCHAEV
$$
1\ 3\ 2\ 4\quad   1\ 2\ 3\ 4 \quad 1\ 2\ 4\ 3\quad   2\ 1\ 3\ 4\quad   2\ 
1\ 4\ 3   \quad 3\ 1\ 4\ 2
$$
NAHODIM, CHTO $A_4=1+0+1+1+2+3=8$. chTOBY ISSLEDOVATX $A_n$ V OBSHCHEM SLUCHAE, 
RASSMOTRIM RESHETCHATUYU DIAGRAMMU NA RIS.~11 DLYA $n=15$. v TAKOJ DIAGRAMME 
2-UPORYADOCHENNUYU PERESTANOVKU MOZHNO PREDSTAVITX V VIDE PUTI IZ VERHNEJ 
LEVOJ UGLOVOJ TOCHKI $(0, 0)$ V NIZHNYUYU PRAVUYU UGLOVUYU TOCHKU $(\ceil{n/2}, 
\floor{n/2})$, ESLI DELATX $k$-J SHAG PUTI VPRAVO ILI VNIZ V SOOTVETSTVII S 
TEM, NAHODITSYA LI $k$ V CHETNOJ ILI NECHETNOJ POZICII PERESTANOVKI. eTIM 
PRAVILOM OPREDELYAETSYA VZAIMNO ODNOZNACHNOE SOOTVETSTVIE MEZHDU 
2-UPORYADOCHENNYMI PERESTANOVKAMI I $n$-SHAGOVYMI PUTYAMI IZ ODNOGO UGLA 
RESHETCHATOJ DIAGRAMMY V DRUGOJ. nAPRIMER, IZOBRAZHENNYJ NA RISUNKE PUTX 
SOOTVETSTVUET PERESTANOVKE
$$
2\ 1\ 3\ 4\ 6\ 5\ 7\ 10\ 8\ 11\ 9\ 12\ 14\ 13\ 15.
\eqno(1)
$$
dALEE, VERTIKALXNYM OTREZKAM PUTI MOZHNO PRIPISATX "VESA", KAK POKAZANO NA 
DIAGRAMME; OTREZKU, VEDUSHCHEMU IZ TOCHKI $(i, j)$
%% 110
V TOCHKU $(i+1, j)$ PRIPISYVAETSYA VES $\abs{i-j}$. nEMNOGO PODUMAV,
CHITATELX UBEDITSYA V TOM, CHTO SUMMA |TIH VESOV VDOLX KAZHDOGO PUTI RAVNA 
CHISLU INVERSIJ V SOOTVETSTVUYUSHCHEJ PERESTANOVKE (SM. UPR.~12). tAK, NAPRIMER,
PERESTANOVKA (1) SODERZHIT 
$1+0+1+0+1+2+1=6$ INVERSIJ.

eSLI $a\le a'$ I~$b\le b'$, TO CHISLO DOPUSTIMYH PUTEJ IZ $(a, b)$ V 
$(a', b')$ RAVNO CHISLU SPOSOBOV PEREMESHATX $a'-a$ VERTIKALXNYH OTREZKOV 
S $b'-b$ GORIZONTALXNYMI, A IMENNO
$$
\perm{a'-a+b'-b}{a'-a}.
$$
sLEDOVATELXNO, CHISLO PERESTANOVOK, DLYA KOTORYH SOOTVETSTVUYUSHCHIE PUTI 
PROHODYAT CHEREZ VERTIKALXNYJ OTREZOK IZ $(i, j)$ V~$(i+1, j)$, RAVNO
$$
\perm{i+j}{i}\perm{n-i-j-1}{\floor{n/2}-j}.
$$
uMNOZHAYA |TO ZNACHENIE NA VES DANNOGO OTREZKA I SUMMIRUYA PO VSEM OTREZKAM, POLUCHAEM
$$
\eqalign{
A_{2n}&=\sum_{0\le i\le n \atop 0\le j\le n}
\abs{i-j}\perm{i+j}{i}\perm{2n-i-j-1}{n-j};\cr
A_{2n+1}&=\sum_{0\le i\le n \atop 0\le j\le n}
\abs{i-j}\perm{i+j}{i}\perm{2n-i-j}{n-j};\cr
}
\eqno(2)
$$
zNAKI ABSOLYUTNOJ VELICHINY V |TIH SUMMAH NESKOLXKO USLOZHNYAYUT VYCHISLENIYA, NO 
V UPR.~14 POKAZANO, CHTO VELICHINA $A_n$ IMEET UDIVITELXNO PROSTOJ VID: 
$\floor{n/2}2^{n-2}$. sLEDOVATELXNO, SREDNEE CHISLO INVERSIJ V SLUCHAJNOJ 
2-UPORYADOCHENNOJ PERESTANOVKE RAVNO
$$
\floor{n/2}2^{n-2}/\perm{n}{\floor{n/2}}.
$$
pO FORMULE sTIRLINGA |TA VELICHINA ASIMPTOTICHESKI PRIBLIZHAETSYA K 
$\sqrt{\pi/128}n^{3/2}\approx 0.15 n^{3/2}$. kAK LEGKO VIDETX, 
MAKSIMALXNOE CHISLO INVERSIJ RAVNO
$$
\perm{\floor{n/2}+1}{2}\approx{1\over8}n^2.
$$
pOLEZNO ISSLEDOVATX RASPREDELENIE CHISLA INVERSIJ BOLEE TSHCHATELXNO, 
RASSMOTREV PROIZVODYASHCHIE FUNKCII
$$
\matrix{
 h_1(z)=1, \quad h_2(z)=1+z,\cr
 h_3(z)=1+2z, \quad h_4(z)=1+3z+z^2+z^3, \ldots,\cr
}
\eqno(3)
$$
%% 111
KAK V UPR. 15. tAKIM OBRAZOM, NAJDEM, CHTO STANDARTNOE OTKLONENIE TOZHE 
PROPORCIONALXNO $n^{3/2}$, TAK CHTO CHISLO INVERSIJ NE SLISHKOM USTOJCHIVO 
RASPREDELENO OKOLO SVOEGO SREDNEGO ZNACHENIYA. rASSMOTRIM TEPERX OBSHCHIJ 
DVUHPROHODNYJ SLUCHAJ ALGORITMA D, KOGDA SHAGI SORTIROVKI RAVNY $h$ I~1.

\proclaim tEOREMA H. sREDNEE CHISLO INVERSIJ V $h$-UPORYADOCHENNOJ 
PERESTANOVKE MNOZHESTVA $\{1, 2, \ldots, n\}$ RAVNO
$$
f(n, h)={2^{2q-1}q!q! \over (2q+1)!}\left(\left({h\over2}\right)q(q+1)+
\left({r\over2}\right)(q+1)-{1\over2}\perm{h-r}{2}q\right),
\eqno(4)
$$
GDE $q =\floor{n/h}$, $r= n \bmod h$.
eTA TEOREMA PRINADLEZHIT dUGLASU hANTU [Bachelor's thesis, Princeton 
University (April, 1967)]. zAMETIM, CHTO FORMULA SPRAVEDLIVA I PRI 
$h\ge n: f (n, h) ={1\over2}\left({n\over2}\right)$.
\proof v $h$-UPORYADOCHENNOJ PERESTANOVKE SODERZHITSYA 
$r$ UPORYADOCHENNYH PODPOSLEDOVATELXNOSTEJ DLINY $q+1$ I $h-r$ 
PODPOSLEDOVATELXNOSTEJ DLINY $q$. kAZHDAYA INVERSIYA OBRAZUETSYA 
IZ |LEMENTOV DVUH RAZLICHNYH PODPOSLEDOVATELXNOSTEJ, A KAZHDAYA PARA 
RAZLICHNYH UPORYADOCHENNYH PODPOSLEDOVATELXNOSTEJ V SLUCHAJNOJ 
$h$-UPORYADOCHENNOJ PERESTANOVKE OPREDELYAET SLUCHAJNUYU 2-UPORYADOCHENNUYU 
PERESTANOVKU. pO|TOMU SREDNEE CHISLO INVERSIJ RAVNO SUMME SREDNIH ZNACHENIJ 
CHISLA INVERSIJ VO VSEH PARAH RAZLICHNYH PODPOSLEDOVATELXNOSTEJ, A IMENNO
$$
\perm{r}{2}{A_{2q+2}\over\perm{2q+2}{q+1}}
+r(h-r){A_{2q+1}\over\perm{2q+1}{q}}
+\perm{h-r}{2}{A_{2q}\over\perm{2q}{q}}=f(n,h).\;\endmark
$$
\eproofend

\proclaim sLEDSTVIE. eSLI POSLEDOVATELXNOSTX PRIRASHCHENIJ UDOVLETVORYAET USLOVIYU
$$
h_{s+1}\bmod h_s=0\rem{ PRI $t>s\ge 1$,}
\eqno(5)
$$
TO SREDNEE CHISLO OPERACIJ PEREMESHCHENIYA V ALGORITME D RAVNO
$$
\sum_{t\ge s\ge 1}
 (r_sf(q_s+1, h_{s+1}/h_s)+(h_s-r_s)f(q_s, h_{s+1}/h_s)),
\eqno(6)
$$
GDE $r_s=N\bmod h_s$, $q_s=\floor{N/h_s}$, $h_{t+1}=Nh_t$, A FUNKCIYA $f$ 
OPREDELYAETSYA FORMULOJ (4).

\proof pROCESS $h_s$-SORTIROVKI SOSTOIT IZ SORTIROVKI PROSTYMI VSTAVKAMI 
$r_s(h_{s+1}/h_s)$-UPORYADOCHENNYH PODFAJLOV DLINY $q_s+1$ 
I~$(h_s-r_s)$ TAKIH PODFAJLOV DLINY $q_s$. pOSKOLXKU MY PREDPOLAGAEM, CHTO 
ISHODNAYA PERESTANOVKA SLUCHAJNA I VSE EE |LEMENTY RAZLICHNY, TO IZ USLOVIJ 
DELIMOSTI SLEDUET, CHTO KAZHDYJ IZ PODFAJLOV---"SLUCHAJNAYA" 
$(h_{s+1}/h_s)$-UPORYADOCHENNAYA
%%112
PERESTANOVKA V TOM SMYSLE, CHTO VSE 
$(h_{s+1}/h_s)$-UPORYADOCHENNYE PERESTANOVKI RAVNOVEROYATNY.
\proofend

uSLOVIE (5) |TOGO SLEDSTVIYA VSEGDA VYPOLNYAETSYA DLYA \emph{DVUHPROHODNOJ} 
SORTIROVKI METODOM shELLA, KOGDA SHAGI RAVNY SOOTVETSTVENNO $h$ I~1. 
pUSTX $q=\floor{N/h}$, a~$r=N\bmod h$, TOGDA SREDNEE ZNACHENIE VELICHINY $B$ 
V PROGRAMME D RAVNO
$$
rf(q+1, N)+(h-r)f(q, N)+f(N,h)
={r\over2}\perm{q+1}{2}+{h-r\over2}\perm{q}{2}+f(N,h).
$$
v PERVOM PRIBLIZHENII FUNKCIYA $f(n, h)$ RAVNA $(\sqrt{\pi}/8)n^{3/2}h^{1/2}$;
SR. S GLADKOJ KRIVOJ NA RIS.~12. sLEDOVATELXNO, VREMYA RABOTY
\picture{rIS. 12. sREDNEE CHISLO INVERSIJ $f(n, h)$ V $h$-UPORYADOCHENNOM 
FAJLE IZ $n$ |LEMENTOV DLYA SLUCHAYA $n=64$.}
DVUHPROHODNOJ PROGRAMMY D PRIMERNO PROPORCIONALXNO 
$2N^2/h+\sqrt{\pi N^3h}$. pO|TOMU NAILUCHSHEE ZNACHENIE $h$ RAVNO 
PRIBLIZITELXNO $\root 3\of{16N/\pi}\approx1.72\root3\of{N}$; PRI TAKOM 
VYBORE $h$ SREDNEE VREMYA RABOTY PROPORCIONALXNO $N^{5/3}$.

tAKIM OBRAZOM, DAZHE PRIMENYAYA METOD shELLA S VSEGO DVUMYA SHAGAMI, MOZHNO 
SUSHCHESTVENNO SOKRATITX VREMYA PO SRAVNENIYU S PROSTYMI VSTAVKAMI, S $O(N^2)$ 
DO~$O(N^{1.667})$. yaSNO, CHTO MOZHNO DOBITXSYA LUCHSHIH REZULXTATOV, ESLI 
ISPOLXZOVATX BOLXSHE SHAGOV. v UPR.~18 OBSUZHDAETSYA OPTIMALXNYJ VYBOR 
$h_t$,~\dots, $h_1$ PRI FIKSIROVANNOM~$t$
%%113
V SLUCHAE, KOGDA ZNACHENIYA $h$ OGRANICHENY 
USLOVIEM DELIMOSTI; VREMYA RABOTY PRI BOLXSHIH $N$ SOKRASHCHAETSYA 
DO $O(N^{1.5+\varepsilon/2}$ GDE $\varepsilon=1/(2^t-1)$. eSLI MY 
POLXZUEMSYA PRIVEDENNYMI VYSHE FORMULAMI, BARXER $N^{1.5}$ PREODOLETX 
NEVOZMOZHNO, POTOMU CHTO PRI POSLEDNEM PROSMOTRE V SUMMU INVERSIJ VSEGDA VNOSITSYA VKLAD
$$
f(N, h_2)\approx(\sqrt{\pi}/8)N^{3/2}h_2^{1/2}.
$$

nO INTUICIYA PODSKAZYVAET, CHTO, ESLI SHAGI $h_t$, \dots, $h_1$ 
\emph{NE BUDUT} UDOVLETVORYATX USLOVIYU DELIMOSTI (5), MOZHNO 
DOSTICHX BOLXSHEGO. nAPRIMER, PRI POSLEDOVATELXNOM VYPOLNENII 8-, 4- I 
2-SORTIROVOK NEVOZMOZHNO VZAIMODEJSTVIE MEZHDU KLYUCHAMI V CHETNYH I NECHETNYH 
POZICIYAH; PO|TOMU NA DOLYU ZAKLYUCHITELXNOJ 1-SORTIROVKI OSTANETSYA 
$O(N^{3/2})$ INVERSIJ. v TO ZHE VREMYA PRI POSLEDOVATELXNOM VYPOLNENII 7-, 
5- I 3-SORTIROVOK FAJL PERETRYAHIVAETSYA TAK, CHTO PRI ZAKLYUCHITELXNOJ 
1-SORTIROVKE NE MOZHET VSTRETITXSYA BOLEE $2N$ INVERSIJ! (sM. UPR.~26.) nA 
SAMOM DELE NABLYUDAETSYA UDIVITELXNOE YAVLENIE.

\proclaim tEOREMA k. pOSLE $h$-SORTIROVKI $k$-UPORYADOCHENNYJ FAJL OSTAETSYA $k$-UPORYADOCHENNYM.

tAKIM OBRAZOM, FAJL, KOTORYJ BYL SNACHALA 7-OTSORTIROVAN, A POTOM 
5-OTSORTIROVAN, STANOVITSYA ODNOVREMENNO. 7- I 5-UPORYADOCHENNYM. a ESLI MY 
PODVERGNEM EGO 3-SORTIROVKE, TO POLUCHENNYJ FAJL BUDET 7-, 5- I 
3-UPORYADOCHEN. pRIMERY PROYAVLENIYA |TOGO ZAMECHATELXNOGO SVOJSTVA MOZHNO NAJTI 
V TABL. 4.
\picture{tABLICA 4  sORTIROVKA S UBYVAYUSHCHIM SHAGOM (7, 5, 3, 1)}
\proof v UPR.~20 POKAZANO, CHTO |TA TEOREMA VYTEKAET IZ SLEDUYUSHCHEJ LEMMY:

%%114

\proclaim lEMMA L. pUSTX $m$, $n$, $r$---NEOTRICATELXNYE CELYE CHISLA, 
A $x_1$, \dots, $x_{m+r}$ I~$y_1$, \dots, $y_{n+r}$---PROIZVOLXNYE 
POSLEDOVATELXNOSTI CHISEL, TAKIE, CHTO
$$
y_1\le x_{m+1}, y_2\le x_{m+2}, \ldots, y_r\le x_{m+r}.
\eqno(7)
$$
eSLI POSLEDOVATELXNOSTI $x$ I~$y$ OTSORTIROVATX NEZAVISIMO, TAK CHTO 
$x_1\le\ldots\le x_{m+r}$ I~$y_1\le\ldots\le y_{n+r}$, TO SOOTNOSHENIYA (7) 
OSTANUTSYA V SILE.

\proof iZVESTNO, CHTO VSE, KROME, BYTX MOZHET, $m$ |LEMENTOV 
POSLEDOVATELXNOSTI $x$, PREVOSHODYAT (T. E. BOLXSHE ILI RAVNY) NEKOTORYE 
|LEMENTY POSLEDOVATELXNOSTI $y$, PRICHEM RAZLICHNYE |LEMENTY $x$ 
PREVOSHODYAT RAZLICHNYE |LEMENTY $y$. pUSTX $1\le j\le r$. tAK KAK POSLE 
SORTIROVKI |LEMENT $x_{m+j}$ PREVOSHODIT $m+j$ |LEMENTOV $x$, TO ON 
PREVOSHODIT PO KRAJNEJ MERE $j$ |LEMENTOV $y$, A ZNACHIT, ON PREVOSHODIT 
$j$ \emph{NAIMENXSHIH} |LEMENTOV $y$. sLEDOVATELXNO, POSLE SORTIROVKI IMEEM 
$x_{m+j}\ge y_j$.
\endmark\hskip 1em
%\proofend
\proofend

iZ TEOREMY k VIDNO, CHTO PRI SORTIROVKE ZHELATELXNO POLXZOVATXSYA VZAIMNO 
PROSTYMI ZNACHENIYAMI SHAGOV, ODNAKO NEPOSREDSTVENNO IZ NEE NE SLEDUYUT 
TOCHNYE OCENKI CHISLA PEREMESHCHENIJ, VYPOLNYAEMYH ALGORITMOM D. tAK KAK CHISLO 
PERESTANOVOK MNOZHESTVA $\{1, 2, \dots, n\}$, ODNOVREMENNO $h$- I 
$k$-UPORYADOCHENNYH, NE VSEGDA YAVLYAETSYA DELITELEM $n!$, TO PONYATNO, CHTO 
TEOREMA k OB®YASNYAET DALEKO NE VSE; V REZULXTATE $k$- I $h$-SORTIROVOK 
NEKOTORYE $k$- I $h$-UPORYADOCHENNYE FAJLY POLUCHAYUTSYA CHASHCHE DRUGIH. 
bOLEE TOGO, NE SUSHCHESTVUET OCHEVIDNOGO SPOSOBA OTYSKATX "NAIHUDSHIJ SLUCHAJ" 
DLYA ALGORITMA D PRI PROIZVOLXNOJ POSLEDOVATELXNOSTI SHAGOV SORTIROVKI $h_t$,
 \dots, $h_1$. pO|TOMU DO SIH POR VSE POPYTKI ANALIZA |TOGO ALGORITMA V 
OBSHCHEM SLUCHAE BYLI TSHCHETNY; PO SUSHCHESTVU, VSE, CHTO NAM IZVESTNO,---|TO 
PRIBLIZHENNOE ASIMPTOTICHESKOE POVEDENIE MAKSIMALXNOGO VREMENI RABOTY V NEKOTORYH SLUCHAYAH.

\proclaim tEOREMA P. eSLI $h_s= 2^s-1$ PRI 
$1\le s\le t=\floor{\log_2 N}$, TO VREMYA RABOTY ALGORITMA D ESTX $O(N^{3/2})$

\proof dOSTATOCHNO NAJTI OCENKU $B_s$ CHISLA PEREMESHCHENIJ PRI $s$-M PROSMOTRE,
 TAKUYU, CHTOBY $B_t+\cdots+B_1=O(N^{3/2})$. dLYA PERVYH $t/2$ PROSMOTROV PRI 
$t\le s\ge t/2$ MOZHNO VOSPOLXZOVATXSYA OCHEVIDNOJ OCENKOJ 
$B_s=O(h_s(N/h_s)^2)$, a DLYA POSLEDUYUSHCHIH PROSMOTROV MOZHNO PRIMENITX 
REZULXTAT UPR.~23: $B_s=O(Nh_{s+2}h_{s+1}/h_s)$. sLEDOVATELXNO, 
$B_t+\cdots+B_1=O(N (2 + 2^2 +\cdots+2^{t/2}++2^{t/2}+\cdots+2))=O(N^{3/2})$.
\proofend

eTA TEOREMA PRINADLEZHIT a.~a.~pAPERNOVU I g.~v.~sTASEVICHU [{\sl pROBLEMY 
PEREDACHI INFORMACII\/}, 1,3 (1965), 81--98]. oNA DAET VERHNYUYU OCENKU 
\emph{MAKSIMALXNOGO} VREMENI RABOTY ALGORITMA, A NE
%%115
\ctable{
\hfill\bskip$#$\bskip\hfill&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\rightline{\it tABLICA 5}}
\noalign{\centerline{\bf aNALIZ ALGORITMA D PRI $N=8$}}
\multispan{3}\hbox{shAGI} & A_{ave} & B_{ave} & S & T & \hbox{VREMYA MASHINY \MIX}\cr
  &   &1 & 1.718 &14.000 & 1 & 1 & 204.85u\cr
  & 2 & 1& 2.667 & 9.657 & 3 & 2 & 235.91u\cr
  & 3 & 1& 2.917 & 9.100 & 4 & 2 & 220.16u\cr
  & 4 & 1& 3.083 &10.000 & 5 & 2 & 217.75u\cr
  & 5 & 1& 2.601 &10.000 & 6 & 2 & 210.00u\cr
  & 6 & 1& 2.135 &10.667 & 7 & 3 & 206.60u\cr
  & 7 & 1& 1.718 &12.000 & 8 & 2 & 208.85u\cr
4 & 2 & 1& 3.500 & 8.324 & 7 & 3 & 272.32u\cr
5 & 3 & 1& 3.301 & 8.167 & 9 & 3 & 251.60u\cr
3 & 2 & 1& 3.320 & 7.829 & 6 & 3 & 278.50u\cr
}
PROSTO OCENKU \emph{SREDNEGO} VREMENI RABOTY. eTOT REZULXTAT NETRIVIALEN,
 POSKOLXKU MAKSIMALXNOE VREMYA RABOTY V SLUCHAE, KOGDA PRIRASHCHENIYA $h$ 
UDOVLETVORYAYUT USLOVIYU DELIMOSTI (5), IMEET PORYADOK $N^2$, A V UPR.~24 
DOKAZANO, CHTO POKAZATELX $3/2$ UMENXSHITX NELXZYA.

iNTERESNOE ULUCHSHENIE PO SRAVNENIYU S TEOREMOJ P OBNARUZHIL V 1969~G. vOGAN 
pRATT. \dfn{eSLI VSE SHAGI SORTIROVKI VYBIRAYUTSYA IZ MNOZHESTVA CHISEL VIDA 
$2^p3^q$, MENXSHIH $N$, TO VREMYA RABOTY ALGORITMA D BUDET PORYADKA 
$N (\log N)^2$}. v |TOM SLUCHAE TAKZHE MOZHNO VNESTI V ALGORITM NESKOLXKO SUSHCHESTVENNYH 
UPROSHCHENIJ. k SOZHALENIYU, METOD pRATTA TREBUET SRAVNITELXNO BOLXSHOGO CHISLA 
PROSMOTROV, TAK CHTO |TO NE LUCHSHIJ SPOSOB VYBORA SHAGOV, ESLI TOLXKO $N$ NE 
OCHENX VELIKO; SM. UPR.~30 I~31.

rASSMOTRIM \emph{OBSHCHEE} VREMYA RABOTY PROGRAMMY D, 
IMENNO $(9B+10NT+13T-10S-3A+1)u$. v TABL.~5 POKAZANO SREDNEE VREMYA RABOTY 
DLYA RAZLICHNYH POSLEDOVATELXNOSTEJ SHAGOV PRI $N=8$. kAZHDYJ |LEMENT TABLICY 
MOZHNO VYCHISLITX S POMOSHCHXYU FORMUL, PRIVEDENNYH VYSHE ILI V UPR.~19, ZA 
ISKLYUCHENIEM SLUCHAEV, KOGDA SHAGI RAVNY $5$ $3$ $1$ I $3$ $2$ $1$; DLYA |TIH 
DVUH SLUCHAEV BYLO PROVEDENO TSHCHATELXNOE ISSLEDOVANIE VSEH $8!$ 
PERESTANOVOK. zAMETIM, CHTO PRI TAKOM MALOM ZNACHENII $N$ V OBSHCHEM VREMENI 
RABOTY PREOBLADAYUT VSPOMOGATELXNYE OPERACII, PO|TOMU NAILUCHSHIE REZULXTATY 
POLUCHAYUTSYA PRI $t=1$; SLEDOVATELXNO, PRI $N=8$ LUCHSHE VSEGO POLXZOVATXSYA 
PROSTYMI VSTAVKAMI. (sREDNEE VREMYA RABOTY PROGRAMMY S PRI $N=8$ RAVNO 
VSEGO $191.85u$.) lYUBOPYTNO, CHTO NAILUCHSHIJ REZULXTAT V DVUHPROHODNOM 
ALGORITME DOSTIGAETSYA PRI $h_2=6$, POSKOLXKU BOLXSHAYA VELICHINA 
5 OKAZYVAETSYA VAZHNEE MALOJ VELICHINY~$B$. aNALOGICHNO TRI SHAGA $3$ $2$ $1$ 
MINIMIZIRUYUT SREDNEE CHISLO PEREMESHCHENIJ, NO |TO NE SAMAYA
%% 116
LUCHSHAYA POSLEDOVATELXNOSTX DLYA TREH PROSMOTROV. bYTX MOZHET, INTERESNO 
PRIVESTI NEKOTORYE "NAIHUDSHIE" PERESTANOVKI, MAKSIMIZIRUYUSHCHIE CHISLO 
PEREMESHCHENIJ, TAK KAK OBSHCHIJ SPOSOB POSTROENIYA TAKIH PERESTANOVOK DO SIH POR 
NE IZVESTEN:
$$
\matrix{
h_3=5, & h_2=3, & h_1=1: & 8 & 5 & 2 & 6 & 3 & 7 & 4 & 1 & \hbox{(19 PEREMESHCHENIJ)}\cr
h_3=3, & h_2=2, & h_1=1: & 8 & 3 & 5 & 7 & 2 & 4 & 6 & 1 & \hbox{(17 PEREMESHCHENIJ)}\cr
}
$$

s ROSTOM $N$ NABLYUDAETSYA NESKOLXKO INAYA KARTINA. v TABL.~6 POKAZANY 
PRIBLIZHENNYE ZNACHENIYA CHISLA PEREMESHCHENIJ DLYA RAZLICHNYH 
POSLEDOVATELXNOSTEJ SHAGOV PRI $N=1000$. pERVYE 
NESKOLXKO POSLEDOVATELXNOSTEJ UDOVLETVORYAYUT USLOVIYU DELIMOSTI (5), TAK CHTO 
MOZHNO VOSPOLXZOVATXSYA FORMULOJ (6); DLYA POLUCHENIYA SREDNIH ZNACHENIJ PRI 
DRUGIH POSLEDOVATELXNOSTYAH SHAGOV PRIMENYALISX |MPIRICHESKIE TESTY. bYLI 
SGENERIROVANY PYATX FAJLOV PO 1000 SLUCHAJNYH |LEMENTOV, I KAZHDYJ FAJL 
SORTIROVALSYA S KAZHDOJ POSLEDOVATELXNOSTXYU SHAGOV.

eTI DANNYE POZVOLYAYUT VYYAVITX NEKOTORYE HARAKTERISTIKI, NO POVEDENIE 
ALGORITMA D VSE ESHCHE OSTAETSYA NEYASNYM. shELL PERVONACHALXNO PREDPOLAGAL 
ISPOLXZOVATX SHAGI $\floor{N/2}$, $\floor{N/4}$, $\floor{N/8}$, \dots NO 
|TO NEZHELATELXNO, ESLI DVOICHNOE PREDSTAVLENIE CHISLA $N$ SODERZHAT DLINNYE 
CEPOCHKI NULEJ. lAZARUS I fR|NK [{\sl CACM\/}, {\bf 3} (1960), 20--22] 
PREDLOZHILI ISPOLXZOVATX, PO SUSHCHESTVU, TU ZHE POSLEDOVATELXNOSTX, NO 
DOBAVLYAYA $1$ TAM, GDE |TO NEOBHODIMO, CHTOBY SDELATX VSE SHAGI NECHETNYMI. 
hIBBARD 
[{\sl CACM\/}, {\bf 6} (1963), 206--213] PREDLOZHIL SHAGI VIDA $2^k-1$; 
pAPERNOV I sTASEVICH PREDLOZHILI POSLEDOVATELXNOSTX $2^k+1$. sREDI DRUGIH 
ESTESTVENNYH POSLEDOVATELXNOSTEJ, ISPOLXZOVANNYH DLYA. POLUCHENIYA 
TABL.~6,---POSLEDOVATELXNOSTI $(2^k-(-1)^k)/3$, $(3^k-1)/2$ I CHISLA fIBONACHCHI.

mINIMALXNOE CHISLO PEREMESHCHENIJ 6600 NABLYUDAETSYA DLYA SHAGOV VIDA $2^k+1$, 
NO VAZHNO PONIMATX, CHTO NADO UCHITYVATX NE TOLXKO CHISLO PEREMESHCHENIJ, HOTYA 
IMENNO ONO ASIMPTOTICHESKI DOMINIRUET V OBSHCHEM VREMENI RABOTY. tAK KAK VREMYA 
RABOTY PROGRAMMY D RAVNO $9B+10NT+\cdots$ EDINIC, YASNO, CHTO |KONOMIYA 
ODNOGO PROSMOTRA PRIMERNO |KVIVALENTNA SOKRASHCHENIYU CHISLA
PEREMESHCHENIJ NA ${10\over9} N$; MY GOTOVY DOBAVITX 1100 PEREMESHCHENIJ,
ESLI ZA SCHET |TOGO UDASTSYA S|KONOMITX ODIN PROSMOTR. 
pO|TOMU PREDSTAVLYAETSYA NERAZUMNYM NACHINATX S $h_t$, BOLXSHEGO, CHEM, 
SKAZHEM, $N/3$, POSKOLXKU BOLXSHOJ SHAG NE UBAVIT CHISLA POSLEDUYUSHCHIH 
PEREMESHCHENIJ NASTOLXKO, CHTOBY OPRAVDATX PERVYJ PROSMOTR.

bOLXSHOE CHISLO |KSPERIMENTOV S ALGORITMOM D PROVELI dZHEJMS pETERSON I 
d|VID~l.~rASSEL V sT|NFORDSKOM UNIVERSITETE V 1971~G. oNI OBNARUZHILI, CHTO DLYA 
SREDNEGO CHISLA PEREMESHCHENIJ $B$ HOROSHIM
%%117
\picture{tABLICA 6.}
%%118
\bye