\input style
%% 118
PRIBLIZHENIEM PRI $100\le N\le 60\ 000$ SLUZHAT SLEDUYUSHCHIE FORMULY:
$$
\displaylines{
\hbox{$1.09N^{1.27}$ ILI $.30N(\ln N)^2-1.35N\ln N$ DLYA POSLEDOVATELXNOSTI 
SHAGOV $2^k+1$,\dots, 9, 5, 3, 1;}\hfill\cr
\hbox{$1.22N^{1.26}$ ILI $.29N(\ln N)^2-1.26N\ln N$ DLYA POSLEDOVATELXNOSTI 
SHAGOV $2^k-1$, \dots, 15, 7, 3, 1;}\hfill\cr
\hbox{$1.12N^{1.28}$ ILI $.36N(\ln N)^2- 1.73N \ln N$ DLYA 
POSLEDOVATELXNOSTI SHAGOV $(2^k\pm 1)/3$, \dots, 11, 5, 3, 1;}\hfill\cr
\hbox{$1.66N^{1.25}$ ILI $.33N(\ln N)^2-1.26N\ln N$ DLYA POSLEDOVATELXNOSTI 
SHAGOV $(3^k-1)/2$, \dots, 40, 13, 4, 1.}\hfill\cr
}
$$
nAPRIMER, PRI $N=20\ 000$ DLYA VSEH |TIH TIPOV SHAGOV 
POLUCHAEM SOOTVETSTVENNO $B\approx 31\ 000$, $33\ 000$, $35\ 000$, 
$39\ 000$. tABL.~7 DAET
\htable{tABLICA 7}%
{kOLICHESTVA PEREMESHCHENIJ PO PROSMOTRAM (PRIMERY DLYA  $N=20 000$)}%
{\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill&\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill&\bskip\hfill$#$\bskip\hfill&\bskip\hfill$#$\bskip\bskip\hfill\cr
h_s & B_s & h_s & B_s & h_s & B_s \cr
\noalign{\hrule}
4095 & 19460 & 4097 & 19550 & 3280 & 25210\cr
2047 & 15115 & 2049 & 14944 & 1093 & 28324\cr
1023 & 15869 & 1025 & 15731 &  364 & 35477\cr
 511 & 18891 &  513 & 18548 &  121 & 47158\cr
 255 & 22306 &  257 & 21827 &   40 & 62110\cr
 127 & 27400 &  129 & 27814 &   13 & 88524\cr
  63 & 35053 &   65 & 33751 &    4 & 74599\cr
  31 & 34677 &   33 & 34303 &    1 & 34666\cr
  15 & 51054 &   17 & 46044\cr
   7 & 40382 &    9 & 35817\cr
   3 & 24044 &    5 & 19961\cr
   1 & 16789 &    3 &  9628\cr
     &       &    1 & 13277\cr
\noalign{\hrule}
}
TIPICHNUYU KARTINU TOGO, KAK RASPREDELYAYUTSYA PEREMESHCHENIYA PO PROSMOTRAM V TREH 
IZ |TIH |KSPERIMENTOV. lYUBOPYTNO, CHTO \emph{OBA} VIDA FUNKCIJ $\alpha N 
(\ln N)^2+\beta N\ln N$ I $\beta N^\alpha$, KAZHETSYA, DOVOLXNO HOROSHO 
SOGLASUYUTSYA S NABLYUDAEMYMI DANNYMI, HOTYA STEPENNAYA FUNKCIYA BYLA 
SUSHCHESTVENNO LUCHSHE PRI MENXSHIH ZNACHENIYAH $N$. dALXNEJSHIE |KSPERIMENTY BYLI 
VYPOLNENY DLYA POSLEDOVATELXNOSTI SHAGOV $2^k-1$ SO ZNACHENIEM $N$, 
DOSTIGAYUSHCHIM $250\ 000$; SOROK PYATX ISPYTANIJ S $N = 250\ 000$ DALI 
ZNACHENIE $B\approx 7\ 900\ 000$ PRI NABLYUDAEMOM STANDARTNOM OTKLONENII 
$50\ 000$. "nAIBOLEE PODHODYASHCHIMI" FORMULAMI DLYA DIAPAZONA $100 \le N \le 
250\ 000$ OKAZALISX SOOTVETSTVENNO $1.21N^{1.26}$ I~$.39N (\ln N)^2- 2.33 
N \ln N$. tAK KAK
%%119
KO|FFICIENTY V PREDSTAVLENII STEPENNOJ FUNKCIEJ OSTALISX POCHTI TAKIMI ZHE, 
V TO VREMYA KAK KO|FFICIENTY V LOGARIFMICHESKOM PREDSTAVLENII DOVOLXNO 
REZKO IZMENILISX, TO RAZUMNO PREDPOLOZHITX, CHTO IMENNO STEPENNAYA FUNKCIYA 
OPISYVAET ISTINNOE ASIMPTOTICHESKOE POVEDENIE METODA shELLA.

eTI |MPIRICHESKIE DANNYE NI KOIM OBRAZOM NE ISCHERPYVAYUT VSEH VOZMOZHNOSTEJ, 
I MY NE POLUCHILI OSNOVANIJ DLYA RESHITELXNYH ZAKLYUCHENIJ O TOM, KAKIE ZHE 
POSLEDOVATELXNOSTI SHAGOV YAVLYAYUTSYA NAILUCHSHIMI DLYA ALGORITMA D. pOSKOLXKU 
PRIRASHCHENIYA VIDA $(3^k-1)/2$ NE UVELICHIVAYUT SUSHCHESTVENNO CHISLA 
PEREMESHCHENIJ I POSKOLXKU DLYA NIH TREBUETSYA LISHX PRIMERNO 5/8 CHISLA 
PROSMOTROV, NEOBHODIMYH DLYA SHAGOV DRUGIH TIPOV, TO, OCHEVIDNO,
 \emph{RAZUMNO VYBIRATX POSLEDOVATELXNOSTX SHAGOV SLEDUYUSHCHIM OBRAZOM:}
$$
\hbox{\it pRINYATX $h_t=1$, $h_{s+1}=3h_s+1$ I OSTANOVITXSYA NA $h_t$, KOGDA 
$h_{t+2}\ge N$.}
\eqno (8)
$$

\section vSTAVKI V SPISOK. oSTAVIM TEPERX METOD shELLA I RASSMOTRIM DRUGIE 
PUTI USOVERSHENSTVOVANIYA PROSTYH VSTAVOK. sREDI OBSHCHIH SPOSOBOV ULUCHSHENIYA 
ALGORITMA ODIN IZ SAMYH VAZHNYH OSNOVYVAETSYA NA TSHCHATELXNOM ANALIZE 
STRUKTUR DANNYH, POSKOLXKU REORGANIZACIYA STRUKTUR DANNYH, POZVOLYAYUSHCHAYA 
IZBEZHATX NENUZHNYH OPERACIJ, CHASTO DAET SUSHCHESTVENNYJ |FFEKT. dALXNEJSHEE 
OBSUZHDENIE |TOJ OBSHCHEJ IDEI MOZHNO NAJTI V \S~2.4, V KOTOROM 
IZUCHAETSYA DOVOLXNO SLOZHNYJ ALGORITM. pOSMOTRIM, KAK ONA PRIMENYAETSYA K 
TAKOMU NEHITROMU ALGORITMU, KAK PROSTYE VSTAVKI. kAKOVA NAIBOLEE 
PODHODYASHCHAYA STRUKTURA DANNYH DLYA ALGORITMA S?

sORTIROVKA PROSTYMI VSTAVKAMI SOSTOIT IZ DVUH OSNOVNYH OPERACIJ:
\medskip
\item{i)} PROSMOTRA UPORYADOCHENNOGO FAJLA DLYA NAHOZHDENIYA NAIBOLXSHEGO 
KLYUCHA, MENXSHEGO ILI RAVNOGO DANNOMU KLYUCHU;

\item{ii)} VSTAVKI NOVOJ ZAPISI V OPREDELENNOE MESTO UPORYADOCHENNOGO FAJLA.
\medskip
\noindent fAJL---|TO, OCHEVIDNO, LINEJNYJ SPISOK, I ALGORITM S OBRABATYVAET 
EGO, ISPOLXZUYA POSLEDOVATELXNOE RASPREDELENIE (P.~2.2.2);
PO|TOMU DLYA VYPOLNENIYA KAZHDOJ OPERACII VSTAVKI NEOBHODIMO PEREMESTITX 
PRIMERNO POLOVINU ZAPISEJ. s DRUGOJ STORONY, NAM IZVESTNO, CHTO DLYA VSTAVOK 
IDEALXNO PODHODIT SVYAZANNOE RASPREDELENIE (P.~2.2.3), TAK KAK PRI |TOM 
TREBUETSYA IZMENITX LISHX NESKOLXKO SVYAZEJ; DRUGAYA OPERACIYA---POSLEDOVATELXNYJ 
PROSMOTR---PRI SVYAZANNOM RASPREDELENII POCHTI TAK ZHE PROSTA, KAK I PRI 
POSLEDOVATELXNOM. pOSKOLXKU SPISKI VSEGDA PROSMATRIVAYUTSYA V ODNOM I TOM 
ZHE NAPRAVLENII, TO DOSTATOCHNO IMETX SPISKI S ODNOJ SVYAZXYU. tAKIM OBRAZOM, 
PRIHODIM K VYVODU, CHTO "PRAVILXNAYA" STRUKTURA DANNYH DLYA METODA PROSTYH 
VSTAVOK---LINEJNYE
%% 120
SPISKI S ODNOJ SVYAZXYU. uDOBNO TAKZHE IZMENITX ALGORITM S, 
CHTOBY SPISOK PROSMATRIVALSYA V  VOZRASTAYUSHCHEM PORYADKE.

\alg L.(vSTAVKI V SPISOK.) pREDPOLAGAETSYA, CHTO ZAPISI $R_1$,\dots, $R_N$ 
SODERZHAT KLYUCHI $K_1$, \dots, $K_N$ I~"POLYA SVYAZI" $L_1$, \dots, $L_N$, V 
KOTORYH MOGUT HRANITXSYA CHISLA OT~0 DO~$N$;
IMEETSYA TAKZHE ESHCHE ODNO POLE SVYAZI $L_0$ V NEKOTOROJ ISKUSSTVENNOJ ZAPISI 
$R_0$ V NACHALE FAJLA. aLGORITM USTANAVLIVAET POLYA SVYAZI TAK, CHTO ZAPISI 
OKAZYVAYUTSYA SVYAZANNYMI V VOZRASTAYUSHCHEM PORYADKE. tAK, ESLI $p(1) \ldots 
p(N)$---"USTOJCHIVAYA" PERESTANOVKA, TAKAYA, CHTO 
$K_{p(1)}\le \ldots \le K_{p(N)}$, TO V REZULXTATE PRIMENENIYA ALGORITMA 
POLUCHIM
$$
L_0=p(1); L_{p(i)}=p(i+1)\ \hbox{PRI $1\le i<N$}; L_{p(N)}=0. 
\eqno(9)
$$
\st[cIKL PO $j$.] uSTANOVITX $L_0\asg N$, $L_N\asg0$. ($L_0$ 
SLUZHIT "GOLOVOJ" SPISKA, A 0---PUSTOJ SVYAZXYU; SLEDOVATELXNO, SPISOK, PO 
SUSHCHESTVU, CIKLICHESKIJ.) vYPOLNITX SHAGI OT \stp{2} DO \stp{5} PRI $j=N-1$, 
$N-2$, \dots, $1$ I ZAVERSHITX RABOTU ALGORITMA.

\st[uSTANOVITX $p$, $q$, $K$.] uSTANOVITX $p\asg L_0$,  $q\asg0$, 
$K\asg K_j$. (v POSLEDUYUSHCHIH SHAGAH MY VSTAVIM ZAPISX $R_j$ V NUZHNOE MESTO V 
SVYAZANNOM SPISKE PUTEM SRAVNENIYA KLYUCHA $K$ S PREDYDUSHCHIMI KLYUCHAMI V 
VOZRASTAYUSHCHEM PORYADKE. pEREMENNYE $p$ I~$q$ SLUZHAT UKAZATELYAMI NA TEKUSHCHEE 
MESTO V SPISKE, PRICHEM $p=L_q$, TAK CHTO $q$ VSEGDA NA ODIN SHAG OTSTAET 
OT $p$.)

\st[sRAVNITX $K$, $K_p$.] eSLI $K\le K_p$, TO PEREJTI K SHAGU \stp{5}. (mY 
NASHLI ISKOMOE POLOZHENIE ZAPISI $R$ V SPISKE MEZHDU $R_q$ I~$R_p$.)

\st[pRODVINUTX $p$, $q$.] uSTANOVITX $q\asg p$, $p\asg L_q$. eSLI $p>0$,
 TO VOZVRATITXSYA K SHAGU \stp{3}. (eSLI $p=0$, TO $K$---NAIBOLXSHIJ KLYUCH, 
OBNARUZHENNYJ DO SIH POR; SLEDOVATELXNO, ZAPISX $R$ DOLZHNA POPASTX V 
KONEC SPISKA, MEZHDU $R_q$ I $R_0$.)

\st[vSTAVITX V SPISOK.] uSTANOVITX $L_q\asg j$, $L_j\asg p$. 
\algend

\ctable{
\strut\bskip\hfill$#:$\hfill\bskip&&\bskip\hfill#\hfill\bskip\cr
\noalign{\rightline{\it tABLICA 8}}
\noalign{\centerline{\bf pRIMER PRIMENENIYA ALGORITMA VSTAVOK V SPISOK}}
\noalign{\hrule}
  j&  0&  1&  2&  3&  4&  5&  6&  7&  8&  9& 10& 11& 12& 13& 14& 15& 16\cr
K_i&---&503&087&512&061&908&170&897&275&653&426&154&509&612&677&765&703\cr
L_j& 16&---&---&---&---&---&---&---&---&---&---&---&---&---&---&---&  0\cr
L_j& 16&---&---&---&---&---&---&---&---&---&---&---&---&---&---&  0& 15\cr
L_j& 14&---&---&---&---&---&---&---&---&---&---&---&---&---& 16&  0& 15\cr
\noalign{\hrule}
}
%% 121
\bye