\input style
\chapno=5\subchno=4
\chapnotrue

%%438
\htable{tABLICA 1}%
{hARAKTERISTIKI OPTIMALXNOGO DEREVA $A_m(n)$, $k_m(n)$ PRI $\alpha=\beta=1$}%
{$n=#$\hfill&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$\hfill&$n=#$\hfill\cr
\omit
  & m=1 &  m=2 & m=3 & m=4 & m=5 & m=6 & m=7 & m=8 & m=9 & m=10& m=11& m=12& \hbox{oPISANIE DEREVA}\cr
1 &  0,0&      &     &     &     &     &     &     &     &     &     &     &-         & 1\cr
2 &  6,2&  0,1 &     &     &     &     &     &     &     &     &     &     &1:1       & 2\cr
3 & 12,3&  6,1 &  0,1&     &     &     &     &     &     &     &     &     &1:1:1     & 3\cr
4 & 20,4& 12,1 &  6,1&  0,1&     &     &     &     &     &     &     &     &1:1:1:1   & 4\cr
5 & 30,5& 18,2 & 12,1&  6,1&  0,1&     &     &     &     &     &     &     &1:1:1:1:1 & 5\cr
6 & 42,2& 24,3 & 18,1& 12,1&  6,1&  0,1&     &     &     &     &     &     & 3:3      & 6\cr
7 & 52,3& 32,3 & 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     &     & 1:3:3    & 7\cr
8 & 62,3& 40,4 & 30,2& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     & 2:3:3    & 8\cr
9 & 72,3& 50,4 & 36,3& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     & 3:3:3    & 9\cr
10& 84,3& 60,5 & 44,3& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     & 3:3:4    &10\cr
11& 96,3& 72,4 & 52,3& 42,2& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     & 3:4:4    &11\cr
12&108,3& 82,4 & 60,4& 48,3& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1& 4:4:4    &12\cr
13&121,4& 92,4 & 70,4& 56,3& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1& 3:3:3:4  &13\cr
14&134,4&102,5 & 80,4& 64,3& 54,2& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1& 3:3:4:4  &14\cr
15&147,4&114,5 & 90,5& 72,3& 60,3& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 3:4:4:4  &15\cr
16&160,4&124,7 &102,4& 80,4& 68,3& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 4:4:4:4  &16\cr
17&175,4&134,8 &112,4& 90,4& 76,3& 66,2& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 4:4:4:5  &17\cr
18&190,4&144,9 &122,4&100,4& 84,3& 72,3& 66,1& 60,1& 54,1& 48,1& 42,1& 36,1& 4:4:5:5  &18\cr
19&205,4&156,9 &132,5&110,4& 92,3& 80,3& 72,1& 66,1& 60,1& 54,1& 48,1& 42,1& 4:5:5:5  &19\cr
20&220,4&168,9 &144,4&120,5&100,4& 88,3& 78,2& 72,1& 66,1& 60,1& 54,1& 48,1& 5:5:5:5  &20\cr
21&236,5&180,9 &154,4&132,4&110,4& 96,3& 84,3& 78,1& 72,1& 66,1& 60,1& 54,1& 4:4:4:4:5&21\cr
22&252,3&192,10&164,4&142,4&120,4&104,3& 92,3& 84,1& 78,1& 72,1& 66,1& 60,1& 4:9:9    &22\cr
23&266,3&204,11&174,5&152,4&130,4&112,3&100,3& 90,2& 84,1& 78,1& 72,1& 66,1& 5:9:9    &23\cr
24&282,3&216,12&186,5&162,5&140,4&120,4&108,3& 96,3& 90,1& 84,1& 78,1& 72,1& 5:9:10   &24\cr
25&296,3&229,12&196,7&174,4&150,5&130,4&116,3&104,3& 96,1& 90,1& 84,1& 78,1& 7:9:9    &25\cr
}
nASH VYVOD VYRAZHENIYA~$(2)$ POKAZYVAET, CHTO VSEGDA, KOGDA ISPOLXZUYUTSYA 
$P+1$~RAVNYH BUFEROV, BUDET IMETX MESTO SOOTNOSHENIE~$\alpha\le\beta$. 
pREDELXNYJ SLUCHAJ~$\alpha=\beta$, POKAZANNYJ V TABL.~1 I NA RIS.~93, 
VOZNIKAET TOGDA, KOGDA TREBUETSYA MINIMIZIROVATX SAMO VREMYA POISKA 
BEZOTNOSITELXNO KO VREMENI PEREDACHI.

vERNEMSYA K NASHEJ PERVONACHALXNOJ ZADACHE. mY ESHCHE NE RASSMOTRELI, KAK 
POLUCHITX NACHALXNYE OTREZKI; BEZ SOVMESHCHENIYA CHTENIYA/ZAPISI/VYCHISLENIJ 
VYBOR S ZAMESHCHENIEM TERYAET NEKOTORYE IZ SVOIH PREIMUSHCHESTV. vOZMOZHNO, NAM 
SLEDUET ZAPOLNITX VSYU VNUTRENNYUYU
\picture{rIS. 93. oPTIMALXNYJ SPOSOB SLIYANIYA 22 NACHALXNYH OTREZKOV RAVNOJ 
DLINY, ESLI V TEOREME n $\alpha=\beta$. eTA SHEMA MINIMIZIRUET VREMYA 
POISKA PRI PREDPOLOZHENIYAH, PRIVEDSHIH K FORMULE (2).
}
PAMYATX, OTSORTIROVATX EE I VYVESTI REZULXTAT; KAZHDUYU IZ TAKIH OPERACIJ 
VVODA I VYVODA MOZHNO VYPOLNITX S ODNIM POISKOM. iLI, VOZMOZHNO, LUCHSHE 
ISPOLXZOVATX, SKAZHEM, 20\% PAMYATI KAK KOMBINIROVANNYJ BUFER VVODA/VYVODA 
I VYPOLNYATX VYBOR S ZAMESHCHENIEM. eTO TREBUET V PYATX RAZ BOLXSHE POISKOV 
(DOPOLNITELXNO PRIMERNO 60~S!), NO UMENXSHAET CHISLO NACHALXNYH OTREZKOV 
SO~100 DO~64; UMENXSHENIE BUDET ESHCHE BOLEE REZKIM, ESLI VVODNYJ FAJL UZHE 
POCHTI UPORYADOCHEN.

eSLI MY RESHILI NE ISPOLXZOVATX VYBOR S ZAMESHCHENIEM, TO OPTIMALXNOE DEREVO 
DLYA $S=100$, $\alpha=0.00145$, $\beta=0.01545$ 
[SM. (2)] OKAZYVAETSYA VESXMA PROZAICHESKIM. eTO PROSTO 10-PUTEVOE SLIYANIE, 
VYPOLNYAEMOE ZA DVA PROHODA PO DANNYM. vYDELYAYA 30~S NA VNUTRENNYUYU 
SORTIROVKU (SKAZHEM, 100~BYSTRYH SORTIROVOK), POLUCHAEM, CHTO NACHALXNYJ 
RASPREDELITELXNYJ PROHOD, ZANIMAET PRIMERNO
$2{1\over2}$~MIN, A KAZHDYJ PROHOD SLIYANIYA ZANIMAET POCHTI 5~MIN; V ITOGE
IMEEM $12.4$~MIN. eSLI MY RESHILI ISPOLXZOVATX VYBOR S ZAMESHCHENIEM, TO 
OPTIMALXNOE DEREVO DLYA $S=64$ OKAZYVAETSYA ODINAKOVO NEINTERESNYM (DVA 
PROHODA 8-PUTEVOGO SLIYANIYA); NACHALXNYJ RASPREDELITELXNYJ PROHOD ZANIMAET 
PRIMERNO $3{1\over2}$~MIN, KAZHDYJ PROHOD SLIYANIYA---OKOLO $4{1\over2}$~MIN, 
OCENKA OBSHCHEGO VREMENI SOSTAVLYAET 12.6~MIN.
%%440
vSPOMNIM, CHTO V OBOIH |TIH METODAH FAKTICHESKI POLNOSTXYU 
ISKLYUCHAETSYA SOVMESHCHENIE CHTENIYA/ZAPISI/VYCHISLENIJ, CHTOBY IMETX BOLXSHIE 
BUFERY (S CELXYU UMENXSHENIYA VREMENI POISKA). nI ODNA IZ |TIH OCENOK NE 
VKLYUCHAET VREMYA, KOTOROE MOZHET POTREBOVATXSYA DLYA OPERACIJ KONTROLXNOGO CHTENIYA.

nA PRAKTIKE POSLEDNIJ PROHOD SLIYANIYA OKAZYVAETSYA OTLICHNYM OT OSTALXNYH; 
NAPRIMER, VYVODNYE DANNYE CHASTO REDAKTIRUYUTSYA I/ILI ZAPISYVAYUTSYA NA LENTU.
 v TAKIH SLUCHAYAH DEREVO, IZOBRAZHAYUSHCHEE SHEMU SLIYANIYA, SLEDUET VYBIRATX S 
ISPOLXZOVANIEM V KORNEVOM UZLE INOGO KRITERIYA OPTIMALXNOSTI.

\section *dRUGOJ SPOSOB RASPREDELENIYA BUFEROV. dAVID~e.~fERGYUSON UKAZAL 
[{\sl CACM,\/} {\bf 14} (1971), 476--478], CHTO MOZHNO UMENXSHITX 
VREMYA POISKA, ESLI NE DELATX VSE BUFERY ODNOGO RAZMERA. tA ZHE MYSLX I 
PRIMERNO V TO ZHE VREMYA PRISHLA V GOLOVU ESHCHE NESKOLXKIM LICAM 
[S.~J.~Waters, {\sl Comp.~J.,\/} {\bf 14} (1971), 109--112; 
Ewing~S.~Walker, Software Age, {\bf 4} (August-September, 1970), 16--17].

pREDPOLOZHIM, CHTO MY VYPOLNYAEM CHETYREHPUTEVOE SLIYANIE OTREZKOV RAVNOJ 
DLINY~$L_0$, IMEYA PAMYATX V $M$~LITER. eSLI MY RAZDELIM PAMYATX NA RAVNYE 
BUFERY RAZMERA~$B=M/5$, TO NAM POTREBUETSYA OKOLO $L_0/B$~POISKOV DLYA 
KAZHDOGO VVODNOGO FAJLA I $4L_0/B$~POISKOV DLYA VYVODA, CHTO V SUMME DAET 
$8L_0/B = 40L_0/M$~POISKOV. nO ESLI MY ISPOLXZUEM CHETYRE BUFERA VVODA 
RAZMERA~$M/6$ I ODIN BUFER VYVODA RAZMERA~$M/3$, TO NAM POTREBUETSYA 
VSEGO LISHX OKOLO $4\times(6L_0/M)+4\times(3L_0/M)=36L_0/M$~POISKOV! 
vREMENA PEREDACHI V OBOIH SLUCHAYAH ODINAKOVY, TAK CHTO MY NICHEGO NE 
POTERYAEM OT |TOGO IZMENENIYA.

v OBSHCHEM SLUCHAE PREDPOLOZHIM, CHTO MY HOTIM SLITX OTSORTIROVANNYE FAJLY, 
IMEYUSHCHIE DLINY~$L_0$,~\dots, $L_p$, V OTSORTIROVANNYJ FAJL 
DLINY~$L_{P+1}=L_1+\cdots+L_P$, I PREDPOLOZHIM, CHTO DLYA $k\hbox{-GO}$FAJLA 
ISPOLXZUETSYA BUFER RAZMERA~$B_k$. tOGDA
$$
B_1+\cdots+B_P+B_{P+1}=M,
\eqno(6)
$$
GDE $M$---OBSHCHIJ OB®EM NALICHNOJ VNUTRENNEJ PAMYATI. chISLO POISKOV BUDET 
PRIBLIZITELXNO RAVNO
$$
{L_1\over B_1}+\cdots+{L_P\over B_P}+{L_{P+1}\over B_{P+1}}.
\eqno(7)
$$
pOPYTAEMSYA MINIMIZIROVATX |TU VELICHINU PRI USLOVII~(6), SCHITAYA DLYA 
UDOBSTVA, CHTO $B_k$ NE OBYAZANY BYTX CELYMI. eSLI UVELICHITX~$B_j$ 
NA~$\delta$ I UMENXSHITX~$B_k$ NA TU ZHE NEBOLXSHUYU VELICHINU, TO CHISLO 
POISKOV IZMENITSYA NA
$$
{L_j\over B_j+\delta}-{L_j\over B_j}+{L_k\over B_k-\delta}-{L_k\over B_k} 
=\left({L_k\over B_k(B_k-\delta)}-{L_j\over B_j(B_j+\delta)}\right)\delta,
$$
T.~E., RASPREDELENIE MOZHNO ULUCHSHITX, ESLI $L_j/B^2_j\ne L_k/B^2_k$. 
sLEDOVATELXNO,
%% 441
MY POLUCHIM MINIMALXNOE CHISLO POISKOV, TOLXKO ESLI
$$
{L_1\over B^2_1}=\cdots={L_P\over B^2_P}={L_{P+1}\over B^2_{P+1}}.
\eqno(8)
$$
tAK KAK MINIMUM OBYAZATELXNO SUSHCHESTVUET, ON DOLZHEN DOSTIGATXSYA PRI
$$
B_k=\sqrt{L_k}M/(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}}),\quad 1\le k\le P+1,
\eqno(9)
$$
POSKOLXKU |TO EDINSTVENNYE ZNACHENIYA~$B_1$,~\dots, $B_{P+1}$, 
UDOVLETVORYAYUSHCHIE ODNOVREMENNO~(6) I~(8). pODSTANOVKA |TIH ZNACHENIJ 
V~(7) DAET VESXMA PROSTUYU FORMULU DLYA OBSHCHEGO CHISLA POISKOV:
$$
(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}})^2/M,
\eqno(10)
$$
KOTORUYU MOZHNO SRAVNITX S CHISLOM $(P+1)(L_1+\cdots+L_{P+1})/M$,
 POLUCHAYUSHCHIMSYA V TOM SLUCHAE, ESLI VSE BUFERY RAVNY PO DLINE.
vYIGRYSH RAVEN~$\sum_{1\le j<k\le P+1}(\sqrt{L_j}-\sqrt{L_k})^2/M$   
SOGLASNO UPR.~1.2.3-31. k SOZHALENIYU, FORMULA (10) NE GODITSYA DLYA PROSTOGO 
OPREDELENIYA OPTIMALXNOJ SHEMY SLIYANIYA, KAK V TEOREME~K (SR.~S UPR.~14).

\section dOPOLNITELXNYE SOOBRAZHENIYA. eSLI ISPOLXZUYUTSYA DVA 
DISKOVYH USTROJSTVA (ODNO DLYA CHTENIYA I ODNO DLYA ZAPISI), TO MOZHNO 
SOVMESTITX CHASTX VREMENI ZAPISI CENOJ DOPOLNITELXNOGO BUFERA VYVODA. 
eSLI ISPOLXZUETSYA METOD "PROGNOZIROVANIYA" (T.~E.~MY SMOTRIM NA POSLEDNIJ 
KLYUCH V KAZHDOM BUFERE VVODA, CHTOBY OPREDELITX, KAKOJ BUFER PERVYM 
OSVOBODITSYA), TO MOZHNO SOVMESTITX CHASTX VREMENI CHTENIYA. k SOZHALENIYU, 
PROSTAYA PROCEDURA SINHRONIZACII, VRODE PROCEDURY V ALGORITME 5.4.6F, NE 
OBESPECHIVAET NEPRERYVNOGO VVODA/VYVODA, TAK KAK MENYAYUSHCHEESYA VREMYA 
CHTENIYA OZNACHAET, CHTO OPERACII VVODA I VYVODA NE BUDUT OKANCHIVATXSYA V ODNO 
VREMYA. tOCHNYJ OB®EM SOVMESHCHENIJ TRUDNO OCENITX, I, VOZMOZHNO, LUCHSHE 
PROMODELIROVATX PROCESS SLIYANIYA, CHTOBY NAJTI KONSTANTY~$\alpha$ I~$\beta$ 
DLYA PRIBLIZHENNOGO VREMENI SLIYANIYA, KAK V TEOREME~H.

eSLI MY ISPOLXZUEM "PLAVAYUSHCHIE" BUFERY (NE PRIPISANNYE K KONKRETNOMU FAJLU),
 TO ONI DOLZHNY BYTX ODNOGO RAZMERA, I TOGDA NELXZYA PRIMENYATX PRIVEDENNUYU 
VYSHE TEHNIKU RASPREDELENIYA BUFEROV; MOZHNO TOLXKO VYBRATX BUFERY VYVODA 
BOLXSHE, CHEM BUFERY VVODA. eSLI ISPOLXZUETSYA $2P$~BUFEROV VVODA 
(VMESTO~$P$), MY SOVMESHCHAEM ZNACHITELXNUYU DOLYU VREMENI VVODA, ODNAKO 
UDVAIVAEM VREMYA POISKA I, VOZMOZHNO, NICHEGO NE VYIGRAEM; PO-VIDIMOMU, 
LUCHSHE VSEGO IMETX $P+1$ ILI $P+2$~BUFEROV VVODA.
tEPERX CHITATELYU DOLZHNO BYTX YASNO, CHTO NIKAKOJ CHETKOJ STRATEGII DLYA 
OPTIMALXNOJ SORTIROVKI NA DISKAH NE RAZRABOTANO;
CHISLO VOZMOZHNYH VARIANTOV ZNACHITELXNO PREVYSHAET CHISLO STRATEGIJ. KOTORYE 
BYLI PROANALIZIROVANY TEORETICHESKI. hOTYA TEORIYA,
%%442
RAZVITAYA V |TOM PUNKTE, DAET NEKOTORYE POLEZNYE PREDSTAVLENIYA, VSE 
ESHCHE TREBUETSYA ZNACHITELXNYJ OB®EM |KSPERIMENTALXNYH ISSLEDOVANIJ.

\section *pODROBNEE OB OPTIMALXNYH DEREVXYAH. v TEOREMAH~H I~K INTERESNO 
RASSMOTRETX KRAJNIJ SLUCHAJ~$\beta=0$, NESMOTRYA NA TO CHTO PRAKTICHESKIE 
SITUACII OBYCHNO PRIVODYAT K PARAMETRAM~$0\le\alpha\le\beta$. kAKOE DEREVO S 
$n$~LISTXYAMI IMEET NAIMENXSHUYU VOZMOZHNUYU DLINU STEPENNOGO PUTI? lYUBOPYTNO, 
CHTO V |TOM SLUCHAE NAILUCHSHIM OKAZYVAETSYA TREHPUTEVOE SLIYANIE.

\proclaim tEOREMA L. dLINA STEPENNOGO PUTI DEREVA S $n$~LISTXYAMI NIKOGDA 
NE MENXSHE, CHEM
$$
f(n)=\cases{
3qn+2(n-3^q), & ESLI $2\cdot 3^{q-1}\le n\le 3^q$;\cr
3qn+4(n-3^q), & ESLI $3^q\le n\le 2\cdot 3^q$.\cr
}
\eqno(11)
$$
tERNARNYE DEREVXYA~$\cJ_n$, OPREDELENNYE PRAVILAMI
\picture{rISUNOK NA STR. 442}
IMEYUT MINIMALXNUYU DLINU STEPENNOGO PUTI.

\proof. vAZHNO ZAMETITX, CHTO $f (n)$---VYPUKLAYA FUNKCIYA, T. E.
$$
f(n+1)-f(n)\ge f(n)-f(n-1) \rem{PRI VSEH $n\ge2$}.
\eqno(13)
$$
eTO SVOJSTVO SUSHCHESTVENNO VVIDU SLEDUYUSHCHEJ LEMMY.

\proclaim lEMMA s. FUNKCIYA~$g(n)$, OPREDELENNAYA NA POLOZHITELXNYH CELYH 
CHISLAH, UDOVLETVORYAET USLOVIYU
$$
\min_{1\le k\le n} (g(k)+g(n-k))=g(\floor{n/2})+g(\ceil{n/2}), 
\quad n\ge 2,
\eqno (14)
$$
TOGDA I TOLXKO TOGDA, KOGDA ONA VYPUKLAYA.

\proof. eSLI $g(n+1)-g(n)<g(n)- g(n-1)$ PRI NEKOTOROM~$n>2$, TO IMEEM 
$g(n+1)+g(n-1)<g(n)+g(n)$, CHTO PROTIVORECHIT~(14). oBRATNO, ESLI~(13) 
IMEET MESTO DLYA~$g$ 
I~$1\le k<n-k$, TO V SILU 
VYPUKLOSTI~$g(k+1)+g(n-k-1)\le g(k)+g(n-k)$.\proofend

pOSLEDNYUYU CHASTX DOKAZATELXSTVA LEMMY s MOZHNO RASPROSTRANITX NA 
LYUBOE~$m\ge2$ I POKAZATX, CHTO
$$
\min_{n_1+\cdots+n_m=n\atop n_1, \ldots, n_m\ge 1}
 (g(n_1)+\cdots+g(n_m))=g(\floor{n/m})+g(\floor{(n+1)/m})+\cdots
+g(\floor{(n+m-1)/m}),
\eqno(15)
$$
%%443
ESLI $g$~VYPUKLA. pUSTX
$$
f_m(n)=f(\floor{n/m})+f(\floor{(n+1)/m})+\cdots+f(\floor{(n+m-1)/m}).
$$
dOKAZATELXSTVO TEOREMY~L ZAVERSHAETSYA DOKAZATELXSTVOM TOGO, 
CHTO $f_3(n)+3n=f(n)$ I~$f_m(n)+mn\ge f(n)$ PRI VSEH~$m\ge2$ (SM.~UPR.~11).\proofend

bYLO BY OCHENX HOROSHO, ESLI BY OPTIMALXNYE DEREVXYA VSEGDA HARAKTERIZOVALISX 
TAK ZHE CHETKO, KAK V TEOREME~L. nO REZULXTATY DLYA $\alpha=\beta$, KOTORYE 
MY VIDIM V TABL.~1, POKAZYVAYUT, CHTO FUNKCIYA~$A_1(n)$ NE VSEGDA VYPUKLA. nA 
SAMOM DELE TABL.~1 DOSTATOCHNO, CHTOBY OPROVERGNUTX BOLXSHINSTVO PROSTYH 
PREDPOLOZHENIJ OB OPTIMALXNYH DEREVXYAH! mY, ODNAKO, MOZHEM SPASTI CHASTX 
TEOREMY~L DLYA SLUCHAYA PROIZVOLXNYH~$\alpha$ I~$\beta$. m.~shLYUMBERGER 
I zh.~vIJEMAN POKAZALI, CHTO \emph{VYSOKIH} PORYADKOV SLIYANIYA VSEGDA MOZHNO 
IZBEZHATX.

\proclaim tEOREMA M. eSLI DANY~$\alpha$ I~$\beta$, KAK V TEOREME~H, TO 
SUSHCHESTVUET OPTIMALXNOE DEREVO, V KOTOROM STEPENX LYUBOGO UZLA NE PREVOSHODIT
$$
d(\alpha, \beta)=\ceil{\min_{k\ge1}\left(k+\left(1+{1\over k}\right)
\left(1+{\beta\over\alpha}\right)\right)}.
\eqno(17)
$$

\proof. pUSTX $n_1$,~\dots, $n_m$---POLOZHITELXNYE CELYE CHISLA, TAKIE, CHTO 
$n_1+\cdots+n_m=n$, $A(n_1)+\cdots+A(n_m)= A_m(n)$, 
$n_1\le \ldots \le n_m$, I PREDPOLOZHIM, CHTO $m\ge d(\alpha, \beta)+1$. 
pUSTX $k$---TO ZNACHENIE, PRI KOTOROM DOSTIGAETSYA MINIMUM V (17); POKAZHEM, CHTO
$$
\alpha n(m-k)+\beta n+A_{m-k}(n)\le \alpha m n +\beta n+A_m(n),
\eqno(18)
$$
I, SLEDOVATELXNO, MINIMUM V (4) VSEGDA DOSTIGAETSYA PRI NEKOTOROM
$m\le d(\alpha, \beta)$.

pO OPREDELENIYU, POSKOLXKU $m\ge k+2$, MY DOLZHNY IMETX
$$
\eqalign{
A_{m-k}(n) &\le A_1(n_1+\cdots+n_{k+1})+A_1(n_{k+2})+\cdots
+A_1(n_m)\le\cr
&\le \alpha(n_1+\cdots+n_{k+1})(k+1)+\beta(n_1+\cdots+n_{k+1})+\cr
&\phantom{\le}+A_1(n_1)+\cdots+A_1(n_m)=\cr
&=(\alpha(k+1)+\beta)(n_1+\cdots+n_{k+1})+A_m(n)\le\cr
&\le(\alpha(k+1)+\beta)(k+1)n/m+A_m(n),\cr
}
$$
OTSYUDA (18) LEGKO VYVODITSYA. (tSHCHATELXNOE RASSMOTRENIE |TOGO 
DOKAZATELXSTVA POKAZYVAET, CHTO OCENKA~(17) YAVLYAETSYA "NAILUCHSHEJ IZ 
VOZMOZHNYH" V TOM SMYSLE, CHTO NEKOTORYE OPTIMALXNYE DEREVXYA DOLZHNY IMETX 
UZLY STEPENI~$d(\alpha, \beta)$; SM. UPR.~13.) \proofend

pOSTROENIE V TEOREME~K TREBUET $O(N^2)$~YACHEEK PAMYATI I $O(N^2\log 
N)$~SHAGOV DLYA VYCHISLENIYA $A_m(n)$ PRI $1\le m\le n\le N$, a
%%444
V TEOREME~M POKAZANO, CHTO TREBUETSYA TOLXKO $O(N)$~YACHEEK I $O(N^2)$~SHAGOV. 
shLYUMBERGER I vIJEMAN OTKRYLI ESHCHE NESKOLXKO OCHENX INTERESNYH SVOJSTV 
OPTIMALXNYH DEREVXEV 
[Optimal disk merge patterns, {\sl Acta Informatica,\/} {\bf 3} (1973), 25--36].

\section iSPOLXZOVANIE SCEPLENIYA. m. a. gOTC 
[{\sl CACM,\/} {\bf 6} (1963), 245--248]
PREDLOZHIL INTERESNYJ SPOSOB, PRI KOTOROM OTDELXNYE DOROZHKI SVYAZYVAYUTSYA 
VMESTE I BLAGODARYA |TOMU ISKLYUCHAETSYA POISK PRI VYVODE. dLYA REALIZACII EGO 
IDEI TREBUETSYA POCHTI NEVOOBRAZIMYJ NABOR PROGRAMM, UPRAVLYAYUSHCHIH DISKAMI, 
NO SAMA IDEYA, KROME SORTIROVKI, PRIMENIMA VO MNOGIH DRUGIH ZADACHAH, I 
PO|TOMU ONA MOZHET PRIVESTI K VESXMA CENNYM METODAM OBSHCHEGO NAZNACHENIYA.

iDEYA PROSTA. vMESTO RAZMESHCHENIYA DOROZHEK POSLEDOVATELXNO VNUTRI CILINDROV 
DISKA MY SVYAZYVAEM IH VMESTE I HRANIM SPISKI SVOBODNOGO PROSTRANSTVA PO 
ODNOMU DLYA KAZHDOGO CILINDRA. kOGDA PRIHODIT VREMYA VYVESTI DOROZHKU 
INFORMACII, MY ZAPISYVAEM EE V TEKUSHCHIJ CILINDR (V TOT, GDE OKAZALSYA 
DERZHATELX GOLOVOK), ESLI |TOT CILINDR NE POLON. pRI |TOM VREMYA 
POISKA OBYCHNO SVODITSYA NA NET.

zDESX NAS PODSTEREGAET LOVUSHKA. dELO V TOM, CHTO MY NE MOZHEM ZAPISYVATX 
SSYLKU NA SLEDUYUSHCHUYU DOROZHKU VNUTRI SAMOJ DOROZHKI, POSKOLXKU NEOBHODIMAYA 
DLYA |TOGO INFORMACIYA V NUZHNYJ MOMENT NE IZVESTNA. (mY MOGLI BY, ESLI |TO 
NAS USTROIT, ZAPISYVATX SSYLKU NA PREDYDUSHCHUYU DOROZHKU I NA 
SLEDUYUSHCHEM PROHODE CHITATX FAJL V OBRATNOM NAPRAVLENII.) mOZHNO 
HRANITX OTDELXNUYU TABLICU ADRESOV SVYAZI DLYA DOROZHEK KAZHDOGO FAJLA,
 VOZMOZHNO, CHASTICHNO NA SAMOM DISKE. sPISKI SVOBODNOGO-PROSTRANSTVA MOZHNO 
KOMPAKTNO PREDSTAVITX S POMOSHCHXYU BITOVYH TABLIC, GDE 1000~BITOV UKAZYVAYUT 
ZANYATOSTX ILI NEZANYATOSTX 1000~DOROZHEK.

\qsection pOMOZHET LI SORTIROVKA KLYUCHEJ? eSLI ZAPISI DLINNYE, A KLYUCHI 
KOROTKIE, VESXMA ZAMANCHIVO SOZDATX NOVYJ FAJL, SOSTOYASHCHIJ TOLXKO IZ KLYUCHEJ 
VMESTE S PORYADKOVYMI NOMERAMI, OPREDELYAYUSHCHIMI IH PERVONACHALXNOE POLOZHENIE V 
FAJLE. pOSLE SORTIROVKI |TOGO FAJLA KLYUCHEJ MOZHNO ZAMENITX KLYUCHI 
POSLEDOVATELXNYMI CHISLAMI~$1$, $2$,~\dots. zATEM |TOT NOVYJ FAJL MOZHNO 
OTSORTIROVATX PO POLOZHENIYU V PERVONACHALXNOM FAJLE, I MY POLUCHIM 
UDOBNOE OPISANIE TOGO, KAK "RASTASOVATX" ZAPISI, CHTOBY PERERAZMESTITX IH V 
TREBUEMOM PORYADKE.

sHEMATICHESKI PREDSTAVIM PROCESS TAK:
\halign{
#\hfill&#\hfill\cr
a) ISHODNYJ FAJL           & $(K_1, I_1)$ $(K_2, I_2)$ \dots $(K_N, I_N)$ DLINNYJ;\cr
b) KLYUCHEVOJ FAJL          & $(K_1, 1)$ $(K_2, 2)$ \dots $(K_N, N)$ KOROTKIJ;\cr
c) OTSORTIROVANNYJ (b)& $(K_{p_1}, p_1)$ $(K_{p_2}, p_2)$\dots $(K_{p_N}, p_N)$ KOROTKIJ;\cr
%%445
d) OTREDAKTIROVANNYJ (S) & $(1, p_1)$ $(2, p_2)$ \dots $(N, p_N)$ KOROTKIJ;\cr
e) OTSORTIROVANNYJ   (d)&  $(q_1, 1)$ $(q_2, 2)$ \dots $(q_N, N)$ KOROTKIJ;\cr
f) OTREDAKTIROVANNYJ (a) & $(q_1, I_1)$  $(q_2, I_2)$ \dots $(q_N, I_n)$ DLINNYJ.\cr
}

\noindent zDESX $p_j=k$ TOGDA I TOLXKO TOGDA, KOGDA $q_k=j$; DVA 
PROCESSA SORTIROVKI V STADIYAH (c) I (c) SRAVNITELXNO BYSTRYE (INOGDA MOZHNO 
OBOJTISX VNUTRENNEJ SORTIROVKOJ), TAK KAK ZAPISI NE SLISHKOM DLINNYE. nA 
STADII (f) MY SVELI ZADACHU K SORTIROVKE FAJLA, KLYUCHI KOTOROGO---PROSTO CHISLA 
$\{1, 2,~\ldots, N\}$; KAZHDAYA ZAPISX TEPERX OPREDELYAET V TOCHNOSTI TO MESTO,
KUDA EE SLEDUET PEREMESTITX.

pROBLEMA VNESHNEGO PERERAZMESHCHENIYA, OSTAYUSHCHAYASYA POSLE STADII (f), KAZHETSYA 
NA PERVYJ VZGLYAD TRIVIALXNOJ, NO FAKTICHESKI ONA OCHENX SLOZHNA, I VSE ESHCHE NE 
NAJDENO NI ODNOGO DEJSTVITELXNO HOROSHEGO ALGORITMA (SUSHCHESTVENNO LUCHSHEGO, 
CHEM SORTIROVKA). mY, OCHEVIDNO, MOGLI BY VYPOLNITX PERERAZMESHCHENIE ZA 
$N$~SHAGOV, PEREMESHCHAYA VSYAKIJ RAZ PO ODNOJ ZAPISI; DLYA 
DOSTATOCHNO BOLXSHOGO~$N$ |TO LUCHSHE, CHEM $N\log N$ V METODAH SORTIROVKI. 
nO $N$ NIKOGDA NE BYVAET TAKIM BOLXSHIM; $N$ POISKOV PROSTO NEREALXNY!

k OTREDAKTIROVANNYM ZAPISYAM MOZHNO |FFEKTIVNO PRIMENYATX KAKOJ-LIBO METOD 
PORAZRYADNOJ SORTIROVKI, TAK KAK KLYUCHI IMEYUT STROGO RAVNOMERNOE 
RASPREDELENIE. nA MNOGIH VYSOKOSKOROSTNYH evm S VYSOKOSKOROSTNYMI 
PERIFERIJNYMI USTROJSTVAMI VREMYA VYCHISLENIJ DLYA VOSXMIPUTEVOGO 
RASPREDELENIYA ZNACHITELXNO MENXSHE, CHEM VREMYA VYCHISLENIJ DLYA 
VOSXMIPUTEVOGO SLIYANIYA; SLEDOVATELXNO, RASPREDELITELXNAYA SORTIROVKA 
MOZHET BYTX NAILUCHSHEJ IZ VSEH PROCEDUR (SM.~P.~5.4.7, A TAKZHE UPR.~17).

nO, PO-VIDIMOMU, BESSMYSLENNO PROVODITX SORTIROVKU KLYUCHEJ LISHX DLYA TOGO,
 CHTOBY VYPOLNITX ZATEM POLNUYU SORTIROVKU! oDNA IZ PRICHIN NEOZHIDANNOJ 
TRUDNOSTI PROBLEMY VNESHNEGO PERERAZMESHCHENIYA BYLA OTKRYTA r.~u.~fLOJDOM, 
KOTORYJ NASHEL NETRIVIALXNUYU NIZHNYUYU GRANICU DLYA CHISLA POISKOV, TREBUEMYH,
 CHTOBY PERESTAVITX ZAPISI V DISKOVOM FAJLE 
[Complexity of Computer Computations (New York, Plenum, 1972), 105--109].

rEZULXTAT fLOJDA UDOBNO OPISATX, VOSPOLXZOVAVSHISX ANALOGIEJ S LIFTOM, 
KAK V P.~5.4.8; NA |TOT RAZ MY HOTIM NAJTI GRAFIK RABOTY LIFTA, 
MINIMIZIRUYUSHCHIJ CHISLO OSTANOVOK, A NE PROJDENNOE RASSTOYANIE. (mINIMIZACIYA 
CHISLA \emph{OSTANOVOK} NE VPOLNE |KVIVALENTNA NAHOZHDENIYU ALGORITMA 
PERERAZMESHCHENIYA S MINIMALXNYM CHISLOM POISKOV, TAK KAK ODNA OSTANOVKA 
OB®EDINYAET VHOD V LIFT S VYHODOM IZ NEGO; ODNAKO RAZNICA NE SLISHKOM VELIKA,
  I MY VOSPOLXZUEMSYA KRITERIEM MINIMIZACII OSTANOVOK, CHTOBY POYASNITX 
OSNOVNYE IDEI.)
%% 446
bUDEM ISPOLXZOVATX FUNKCIYU "DISKRETNOJ |NTROPII"
$$
F(n)=\sum_{1<k\le n}(\ceil{\log_2 k}+1)=B(n)+n-1
=n\ceil{\log_2 n}-2^{\ceil{\log_2 n}}+n,
\eqno(19)
$$
GDE $B(n)$ ESTX FUNKCIYA "BINARNOJ VSTAVKI" (SM. FORMULU (5.3.1-3)). 
sOGLASNO (5.3.1-33), FUNKCIYA $F(n)$ ESTX NE CHTO INOE, KAK MINIMALXNAYA 
DLINA VNESHNEGO PUTI BINARNOGO DEREVA S $n$~LISTXYAMI, I  
$$
n\log_2 n\le F(n)\le n\log_2 n+0.0861n.
\eqno(20)
$$
tAK KAK $F (n)$ VYPUKLA I UDOVLETVORYAET 
USLOVIYU~$F(n)=n+F(\floor{n/2})+F(\ceil{n/2})$, TO PO LEMME~C
$$
F(n)\le F(k)+F(n-k)+n \rem{PRI $0\le k\le n$.}
\eqno(21)
$$
eTO SOOTNOSHENIE VYTEKAET TAKZHE IZ PREDSTAVLENIYA $F$ V VIDE DLINY VNESHNEGO 
PUTI; V DALXNEJSHEM ONO OKAZHETSYA RESHAYUSHCHIM FAKTOM.

kAK I V P.~5.4.8, MY BUDEM PREDPOLAGATX, CHTO LIFT VMESHCHAET $b$~CHELOVEK, 
KAZHDYJ |TAZH VMESHCHAET $c$~CHELOVEK I IMEETSYA $n$~|TAZHEJ. pUSTX $s_{ij}$---CHISLO 
LYUDEJ, NAHODYASHCHIHSYA V DANNYJ MOMENT NA |TAZHE~$i$ I STREMYASHCHIHSYA POPASTX NA 
|TAZH~$j$. pO OPREDELENIYU 
\emph{OCENKA SOVMESTNOSTI} LYUBOGO RASPOLOZHENIYA LYUDEJ V ZDANII 
ESTX~$\sum_{1\le i,j\le n} F(s_{ij})$.

pREDPOLOZHIM, NAPRIMER, CHTO $b=c=n=6$ I CHTO PERVONACHALXNO 36~CHELOVEK 
SLEDUYUSHCHIM OBRAZOM RASPREDELENY MEZHDU |TAZHAMI:
{\obeyspaces
$$
\vbox{
\line{\tt\indent \]\]\]\]\]\]}
\line{\tt\indent 123456 123456 123456 123456 123456 123456 \hfill \rm (22)}
}
$$
}
lIFT PUST I NAHODITSYA NA |TAZHE 1; "\]" OBOZNACHAET SVOBODNOE MESTO. nA 
KAZHDOM |TAZHE NAHODITSYA CHELOVEK, STREMYASHCHIJSYA POPASTX NA PROIZVOLXNYJ |TAZH,
 PO|TOMU VELICHINY~$s_{ij}$. RAVNY~1 I OCENKA SOVMESTNOSTI RAVNA~0. eSLI 
TEPERX LIFT OTVEZET 6~CHELOVEK NA |TAZH~2, TO MY POLUCHIM RASPOLOZHENIE
{\obeyspaces
$$
\vbox{
\line{\tt\indent        123456}
\line{\tt\indent \]\]\]\]\]\] 123456 123456 123456 123456 123456 \hfill 
\rm (23)}
}
$$
}
I OCENKA SOVMESTNOSTI STANET RAVNA $6F(0)+24F(1)+6F(2)=12$. dOPUSTIM, 
LIFT PEREVEZET |1|, |1|, |2|, |3|, |3|, |4| NA |TAZH~3:
{\obeyspaces
$$
\vbox{
\line{\tt\indent               112334}
\line{\tt\indent \]\]\]\]\]\] 245566 123456 123456 123456 123456 \hfill 
\rm (24)}
}
$$
}
%%447
oCENKA SOVMESTNOSTI IZMENILASX DO $4F(2)+2F(3)=18$. kOGDA KAZHDYJ CHELOVEK 
BUDET V KONCE KONCOV PEREVEZEN K SVOEMU MESTU NAZNACHENIYA, OCENKOJ 
SOVMESTNOSTI BUDET $6F(6)=96$.

fLOJD ZAMETIL, CHTO OCENKA SOVMESTNOSTI NIKOGDA NE UVELICHIVAETSYA BOLXSHE, 
CHEM NA $b+c$ ZA ODNU OSTANOVKU, TAK KAK MNOZHESTVO IZ $s$~LYUDEJ S RAVNYM 
NAZNACHENIEM, OB®EDINYAYASX S ANALOGICHNYM MNOZHESTVOM MOSHCHNOSTI~$s'$, 
UVELICHIVAET OCENKU NA $F(s+s')-F(s)-F(s')\le s+s'$. tAKIM OBRAZOM, IMEEM 
SLEDUYUSHCHIJ REZULXTAT.

\proclaim tEOREMA~F. pUSTX $t$---OPREDELENNAYA VYSHE OCENKA SOVMESTNOSTI 
NACHALXNOGO RASPOLOZHENIYA LYUDEJ. lIFT DOLZHEN SDELATX PO KRAJNEJ MERE
$$
\ceil{(nF(c)-t)/(b+c)}
$$
OSTANOVOK, CHTOBY DOSTAVITX VSEH LYUDEJ K IH MESTU NAZNACHENIYA.\endmark


sFORMULIRUEM |TOT REZULXTAT PRIMENITELXNO K DISKAM. dOPUSTIM, IMEETSYA 
$N$~ZAPISEJ PO $B$ V KAZHDOM BLOKE, I PREDPOLOZHIM, CHTO VO VNUTRENNEJ 
PAMYATI ODNOVREMENNO POMESHCHAETSYA $M$~ZAPISEJ. pRI KAZHDOM CHTENII S DISKA ODIN 
BLOK PERENOSITSYA V NAMYATX, A PRI KAZHDOJ ZAPISI ODIN BLOK POMESHCHAETSYA NA 
DISK, I $s_{ij}$ ESTX CHISLO ZAPISEJ V BLOKE~$i$, PRINADLEZHASHCHIH 
BLOKU~$j$. eSLI $N\ge B^2$, TO SUSHCHESTVUET NACHALXNOE RASPOLOZHENIE, DLYA 
KOTOROGO VSE $s_{ij}\le 1$, I, SLEDOVATELXNO, DLYA PERERAZMESHCHENIYA 
ZAPISEJ NEOBHODIMO PROCHITATX PO KRAJNEJ MERE 
$(N/B)F(B)/M\approx (N \log_2 B)/M$~BLOKOV. (eSLI $B$ VELIKO, TO 
MNOZHITELX~$\log_2 B$ DELAET |TU NIZHNYUYU OCENKU NETRIVIALXNOJ, NO ESLI $B=1$,
 TO NIZHNYUYU OCENKU, OCHEVIDNO, MOZHNO ULUCHSHITX.)

\excercises
\ex[M22] v TEKSTE OB®YASNYAETSYA METOD, S POMOSHCHXYU KOTOROGO SREDNEE 
VREMYA OZHIDANIYA, TREBUEMOE DLYA CHTENIYA DOLI~$x$ DOROZHKI, UMENXSHAETSYA 
S~${1\over2}$ 
DO~${1\over2}(1-x^2)$~OBOROTOV. eTO MINIMALXNO VOZMOZHNOE VREMYA, KOGDA 
IMEETSYA ODIN DERZHATELX GOLOVOK. kAKOVO SOOTVETSTVUYUSHCHEE MINIMALXNOE VREMYA 
OZHIDANIYA, ESLI IMEYUTSYA \emph{DVA} DERZHATELYA GOLOVOK, RAZNESENNYE NA 
$180^\circ$ (V PREDPOLOZHENII, CHTO V LYUBOJ MOMENT DANNYE MOZHET PEREDAVATX 
TOLXKO ODIN IZ DERZHATELEJ)?

\ex[M30] (e.~g.~kONHEJM.) cELX |TOJ ZADACHI---ISSLEDOVATX, NA 
KAKOE RASSTOYANIE DOLZHEN PEREMESTITXSYA DERZHATELX GOLOVOK VO VREMYA SLIYANIYA 
FAJLOV, RASPOLOZHENNYH "ORTOGONALXNO" K CILINDRAM dOPUSTIM, IMEETSYA 
$P$~FAJLOV, KAZHDYJ IZ KOTORYH SODERZHIT $L$~BLOKOV ZAPISEJ, I PREDPOLOZHIM,
CHTO PERVYJ BLOK KAZHDOGO FAJLA NAHODITSYA NA CILINDRE~1, VTOROJ---NA 
CILINDRE~2 I T~D dVIZHENIEM DERZHATELYA GOLOVOK VO VREMYA SLIYANIYA UPRAVLYAET 
OTNOSITELXNYJ PORYADOK POSLEDNIH KLYUCHEJ KAZHDOGO BLOKA; SLEDOVATELXNO, 
MOZHNO IZOBRAZITX SITUACIYU SLEDUYUSHCHIM SPOSOBOM, UDOBNYM DLYA MATEMATICHESKOJ
%%448
INTERPRETACII. rASSMOTRIM MNOZHESTVO IZ $PL$ UPORYADOCHENNYH PAR
$$
\matrix{
(a_{11},1) & (a_{21},1) & \ldots & (a_{P1},1) \cr
(a_{12},2) & (a_{22},2) & \ldots & (a_{P2},2) \cr
\vdots & \vdots & & \vdots \cr
(a_{1L},L) & (a_{2L},L) & \ldots & (a_{PL},L) \cr
}
$$
GDE MNOZHESTVO $\{\, a_{ij} \mid 1\le i\le P, 1\le j\le L\,\}$ 
SOOTVETSTVUET MNOZHESTVU CHISEL $\{\,1, 2, \ldots, PL\,\}$ V NEKOTOROM 
PORYADKE I $a_{ij}<a_{i,j+1}$ PRI $1\le j<L$ (STROKI PREDSTAVLYAYUT CILINDRY, 
STOLBCY---ISHODNYE FAJLY). oTSORTIRUEM PARY PO IH PERVYM KOMPONENTAM, I 
PUSTX POLUCHIVSHEJSYA POSLEDOVATELXNOSTXYU BUDET $(1, j_1)$ $(2, j_2)$ \dots{} 
$(PL, j_{PL})$. pOKAZHITE, CHTO ESLI VSE $(PL)!/L!^P$ VOZMOZHLYH 
NABOROV~$a_{ij}$ RAVNOVEROYATNY, TO SREDNEE ZNACHENIE
$$
\abs{j_2-j_1}+\abs{j_3-j_2}+\cdots+\abs{j_{PL}-j_{PL-1}}
$$
RAVNO
$$
(L-1)\left(1+(P-1)2^{2L-2}/\perm{2L}{L}\right).
$$
[\emph{uKAZANIE:} SM. UPR. 5.2.1-14 ] zAMETIM, CHTO PRI  $L\to\infty$ |TO 
ZNACHENIE ASIMPTOTICHESKI RAVNO ${1\over4}(P-1)L\sqrt{\pi L}$.

\ex[m15] pREDPOLOZHIM, CHTO OGRANICHENNYJ RAZMER VNUTRENNEJ PAMYATI DELAET 
NEZHELATELXNYM $10\hbox{-PUTEVOE}$ SLIYANIE. kAK MOZHNO IZMENITX 
REKURRENTNYE SOOTNOSHENIYA (3), (4), (5), CHTOBY $A_1(n)$ STALO MINIMALXNYM 
ZNACHENIEM~$\alpha D(\cJ)+\beta E(\cJ)$ SREDI VSEH DEREVXEV~$\cJ$ S 
$n$~LISTXYAMI, NE IMEYUSHCHIH UZLOV STEPENI, BOLXSHEJ CHEM~9?

\rex[m21] (a) vYVEDITE FORMULU, ANALOGICHNUYU (2), DLYA VREMENI VYPOLNENIYA 
$P\hbox{-PUTEVOGO}$ SLIYANIYA $L$~LITER, ESLI ISPOLXZUETSYA VIDOIZMENENNAYA 
FORMA KVADRATICHNOGO RASPREDELENIYA BUFEROV%
\note{1}{sM. TAKZHE FORMULU (9).---{\sl pRIM. RED.\/}}: VSE $P$~BUFEROV VVODA 
DOLZHNY IMETX RAVNYE DLINY, A RAZMER BUFERA VYVODA SLEDUET VYBRATX TAK, 
CHTOBY MINIMIZIROVATX VREMYA POISKA.

(b) pOKAZHITE, CHTO POSTROENIE V TEOREME~K MOZHNO IZMENITX TAK, CHTO 
POLUCHITSYA SHEMA SLIYANIYA, KOTORAYA BUDET OPTIMALXNOJ V SMYSLE VASHEJ 
FORMULY IZ CHASTI~(a).

\ex[m20] eSLI ISPOLXZUYUTSYA DVA DISKA, PRICHEM CHTENIE S ODNOGO SOVMESHCHAETSYA 
S ZAPISXYU NA DRUGOJ, TO MY NE MOZHEM PRIMENYATX SHEMU SLIYANIYA, PODOBNUYU 
PREDSTAVLENNOJ NA RIS.~93, TAK KAK NEKOTORYE LISTXYA NAHODYATSYA NA CHETNYH 
UROVNYAH, A DRUGIE NA NECHETNYH. pOKAZHITE, KAK IZMENITX POSTROENIE V 
TEOREME~K, CHTOBY POLUCHALISX OPTIMALXNYE DEREVXYA S UCHETOM OGRANICHENIYA, 
CHTO VSE LISTXYA NAHODYATSYA NA CHETNYH UROVNYAH ILI VSE NA NECHETNYH.

\rex[22] nAJDITE DEREVO, OPTIMALXNOE V SMYSLE UPR.~6, ESLI~$n=23$ 
I~$\alpha=\beta=1$. (vOZMOZHNO, U VAS POYAVITSYA ZHELANIE PRIBEGNUTX K POMOSHCHI evm.)

\rex[m24] eSLI DLINY NACHALXNYH OTREZKOV NE RAVNY, TO NAILUCHSHAYA 
SHEMA SLIYANIYA (V SMYSLE TEOREMY~H) MINIMIZIRUET $\alpha D(\cJ)+\beta 
E(\cJ)$, GDE $D(\cJ)$ I~$E(\cJ)$ TEPERX PREDSTAVLYAYUT SOBOJ VZVESHENNYE 
DLINY PUTEJ: KAZHDOMU LISTU DEREVA PRIPISYVAYUTSYA VESA $w_1$,~\dots, $w_n$ 
(SOOTVETSTVUYUSHCHIE DLINAM NACHALXNYH OTREZKOV), A SUMMY STEPENEJ I DLINY 
PUTEJ UMNOZHAYUTSYA NA SOOTVETSTVUYUSHCHIE VESA. nAPRIMER, ESLI $\cJ$---DEREVO, 
PREDSTAVLENNOE NA RIS.~92, TO 
POLUCHIM $D(\cJ)=6w_1+6w_2+7w_3+9w_4+9w_5+7w_6+4w_7+4w_8$, 
$E (\cJ)=2w_1+2w_2+2w_3+3w_4+3w_5+2w_6+w_7+w_8$.

dOKAZHITE, CHTO PRI NEKOTOROM $k$ VSEGDA SUSHCHESTVUET OPTIMALXNAYA SHEMA, V 
KOTOROJ PERVYMI SLIVAYUTSYA $k$ \emph{SAMYH KOROTKIH OTREZKOV}.

%%449

\ex[49] sUSHCHESTVUET, LI ALGORITM, KOTORYJ PRI ZADANNYH $\alpha$, $\beta$ I 
VESAH~$w_1$,~\dots, $w_n$ NAHODIT OPTIMALXNYE V SMYSLE UPR.~7 DEREVXYA, 
ZATRACHIVAYA TOLXKO $O(n^c)$~SHAGOV PRI NEKOTOROM~$c$?

\ex[M49] (shLYUMBERGER I vIJEMAN.) vERNO LI, CHTO DLYA VSEH $n$, $\alpha$ I~$\beta$
SUSHCHESTVUYUT OPTIMALXNYE V SMYSLE TEOREMY~H DEREVXYA S $n$~LISTXYAMI, U 
KOTORYH VSE LISTXYA NAHODYATSYA SAMOE BOLXSHEE NA DVUH SOSEDNIH UROVNYAH? 
eSLI $\alpha$ I~$\beta$ FIKSIROVANY, SUSHCHESTVUET LI CHISLO $m$, TAKOE, CHTO 
DLYA VSEH DOSTATOCHNO BOLXSHIH $n$ IMEET MESTO $A_1(n)=\alpha mn+\beta 
n+A_m(n)$? (oBA |TI PREDPOLOZHENIYA BYLI PROVERENY V SLUCHAE~$\alpha/\beta\ge 4$.)

\ex[vm49] kAKOVO ASIMPTOTICHESKOE POVEDENIE $A_1(n)$ PRI $n\to\infty$ 
PRI ZADANNYH $\alpha$ I~$\beta$?

\ex[m29] v OBOZNACHENIYAH (11) I~(16) DOKAZHITE, CHTO $f_m(n) + mn\ge 
f(n)$ PRI VSEH $m$, $n\ge 2$, I OPREDELITE VSE TIP, PRI KOTORYH IMEET 
MESTO RAVENSTVO.

\ex[25] dOKAZHITE, CHTO PRI VSEH $n>0$ SUSHCHESTVUET DEREVO S $n$~LISTXYAMI I 
MINIMALXNOJ DLINOJ STEPENNOGO PUTI (11), VSE LISTXYA KOTOROGO RASPOLOZHENY 
NA ODNOM UROVNE.

\ex[M24] pOKAZHITE, CHTO PRI $2\le n \le d(\alpha,\beta)$ EDINSTVENNOJ 
NAILUCHSHEJ SHEMOJ SLIYANIYA V SMYSLE TEOREMY~H YAVLYAETSYA $n\hbox{-PUTEVOE}$ 
SLIYANIE. 
(sR. S FORMULOJ (17).)

\ex[40] pRI ISPOLXZOVANII KVADRATICHNOGO METODA RASPREDELENIYA BUFEROV VREMYA 
POISKA DLYA -SHEMY SLIYANIYA NA RIS.~92 BUDET PROPORCIONALXNO
$(\sqrt{2}+\sqrt{4}+\sqrt{1}+\sqrt{1}+\sqrt{8})^2
+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2+\sqrt{1}+\sqrt{2}
+(\sqrt{1}+\sqrt{4})^2+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2$; 
|TO ZNACHENIE PREDSTAVLYAET SOBOJ SUMMU
VELICHIN $(\sqrt{n_1}+\cdots+\sqrt{n_m}+\sqrt{n_1+\cdots+n_m})^2$ PO VSEM 
VNUTRENNIM UZLAM, GDE PODDEREVXYA |TIH UZLOV IMEYUT 
$(n_1, \ldots, n_m)$~LISTXEV. 
nAPISHITE PROGRAMMU DLYA evm, KOTORAYA POROZHDAET DEREVXYA S 
MINIMALXNYM VREMENEM POISKA, IMEYUSHCHIE $1$, $2$, $3$, \dots{} LISTXEV, 
ISPOLXZUYA DLYA OCENKI VREMENI POISKA |TU FORMULU.

\ex[M22] pOKAZHITE, CHTO MOZHNO NESKOLXKO USILITX TEOREMU~F, ESLI 
LIFT PERVONACHALXNO PUST I ESLI $nF(c)\ne t$: V |TOM SLUCHAE NEOBHODIMO NE 
MENEE $\ceil{(nF(c)+b-t)/(b+c)}$~OSTANOVOK.

\ex[23] (r.~u.~fLOJD.) nAJDITE GRAFIK RABOTY LIFTA, PEREVOZYASHCHIJ VSEH LYUDEJ 
IZ~(22) K IH MESTAM NAZNACHENIYA ZA~12 ILI MENXSHEE CHISLO OSTANOVOK. (v~(23) 
POKAZANO POLOZHENIE POSLE ODNOJ, A NE POSLE DVUH OSTANOVOK.)

\ex[25] (b.~t.~bENNET I a.~ch.~mAK-kELLAR, 1971.) rASSMOTRIM SLEDUYUSHCHIJ 
METOD S SORTIROVKOJ KLYUCHEJ, PRODEMONSTRIROVANNYJ NA PRIMERE FAJLA S 10 KLYUCHAMI:
\medskip
\item{a)} iSHODNYJ FAJL: $(50, I_0)$ $(08, I_1)$ $(51, I_2)$ $(06, I_3)$ $(90, I_4)$ $(17, I_5)$ $(89, I_6)$ $(27, I_7)$ $(65, I_8)$ $(42, I_9)$.

\item{b)} fAJL KLYUCHEJ: $(50, 0)$ $(08, 1)$ $(51, 2)$ $(06, 3)$ $(90, 4)$ $(17, 5)$ $(89, 6)$ $(27, 7)$ $(65, 8)$ $(42, 9)$.

\item{c)} oTSORTIROVANNYJ (b): $(06, 3)$ $(08, 1)$ $(17, 5)$ $(27, 7)$ $(42, 9)$ $(50,0)$ $(51,2)$ $(65, 8)$ $(89, 6)$ $(90, 4)$.

\item{d)} pRISVAIVANIE NOMEROV YASHCHIKOV: $(3, 3)$ $(3, 9)$ $(2, 1)$ $(2, 5)$ $(2, 7)$ $(2, 8)$ $(1, 0)$ $(1, 2)$ $(1, 4)$ $(1, 6)$.

\item{e)} oTSORTIROVANNYJ (d): $(1, 0)$ $(2, 1)$ $(1, 2)$ $(3, 3)$ $(1, 4)$ $(2, 5)$ $(1, 6)$ $(2, 7)$ $(2, 8)$ $(3, 9)$.

\item{f)} (a), RASPREDELENNYJ PO YASHCHIKAM S ISPOLXZOVANIEM (e):
\itemitem{yaSHCHIK 1:} $(50, I_0)$ $(51, I_2)$ $(90, I_4)$ $(89, I_6)$.
\itemitem{yaSHCHIK 2:} $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(65, I_8)$.
\itemitem{yaSHCHIK 3:} $(06, I_3)$ $(42, I_9)$.
\item{g)} rEZULXTAT VYBORA S ZAMESHCHENIEM (SNACHALA CHITAETSYA YASHCHIK~3, 
ZATEM YASHCHIK~2, ZATEM YASHCHIK~1): $(06, I_3)$ $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(42, I_9)$ $(50, I_0)$ $(51, I_2)$ $(65, I_8)$ $(89, I_6)$ $(90, I_4)$.
\medskip
\noindent nOMERA YASHCHIKOV NA SHAGE~(d) PRISVAIVAYUTSYA PUTEM PRIMENENIYA K~(S) 
\emph{VYBORA S ZAMESHCHENIEM SPRAVA NALEVO V UBYVAYUSHCHEM} PORYADKE PO VTOROJ KOMPONENTE.
%%450
nOMER YASHCHIKA---|TO NOMER OTREZKA. v PRIVEDENNOM PRIMERE ISPOLXZUETSYA VYBOR S 
ZAMESHCHENIEM TOLXKO S DVUMYA |LEMENTAMI V DEREVE; DLYA VYBORA S ZAMESHCHENIEM 
V~(d) I~(g) DOLZHEN ISPOLXZOVATXSYA ODINAKOVYJ RAZMER DEREVA VYBORA. zAMETIM,
 CHTO SODERZHIMOE YASHCHIKOV NE OBYAZATELXNO UPORYADOCHENO.

dOKAZHITE, CHTO |TOT METOD BUDET SORTIROVATX, T. E. CHTO VYBOR S ZAMESHCHENIEM 
V (g) OBRAZUET LISHX ODIN OTREZOK. (eTOT METOD UMENXSHAET CHISLO YASHCHIKOV, 
TREBUEMOE OBYCHNOJ SORTIROVKOJ KLYUCHEJ POSREDSTVOM RASPREDELENIYA, OSOBENNO 
ESLI ISHODNYE DANNYE UZHE V SILXNOJ STEPENI UPORYADOCHENY.)

\rex[25] nEKOTORYE SISTEMY PREDOSTAVLYAYUT PROGRAMMISTAM 
\emph{VIRTUALXNUYU PAMYATX:} MOZHNO PISATX PROGRAMMY, ISHODYA IZ PREDPOLOZHENIYA,
 CHTO IMEETSYA OCHENX BOLXSHAYA VNUTRENNYAYA PAMYATX, SPOSOBNAYA VMESTITX VSE 
DANNYE. eTA PAMYATX RAZDELENA NA STRANICY, I LISHX NEMNOGIE IZ NIH 
DEJSTVITELXNO NAHODYATSYA VO VNUTRENNEJ PAMYATI V LYUBOJ MOMENT VREMENI, 
OSTALXNYE ZHE HRANYATSYA NA DISKAH ILI BARABANAH. pROGRAMMISTU NE NUZHNO 
VNIKATX VO VSE |TI PODROBNOSTI, TAK KAK SISTEMA SAMA OBO VSEM ZABOTITSYA: 
NOVYE STRANICY AVTOMATICHESKI VYZYVAYUTSYA V PAMYATX, KOGDA ONI NUZHNY.

mOZHET POKAZATXSYA, CHTO POYAVLENIE VIRTUALXNOJ PAMYATI PRIVODIT K OTMIRANIYU 
METODOV VNESHNEJ SORTIROVKI, TAK KAK |TA RABOTA MOZHET BYTX VYPOLNENA 
PROSTO S POMOSHCHXYU METODOV, RAZRABOTANNYH DLYA VNUTRENNEJ 
SORTIROVKI. rAZBERITE |TU SITUACIYU. pOCHEMU SPECIALXNO RAZRABOTANNYJ METOD 
VNESHNEJ SORTIROVKI MOZHET OKAZATXSYA LUCHSHE PRIMENENIYA OBSHCHEJ TEHNIKI 
PODKACHKI STRANIC K METODU VNUTRENNEJ SORTIROVKI?


\subchap{rezyume. istoriya i bibliografiya} % 5.5
tEPERX, KOGDA MY POCHTI DOSTIGLI KONCA |TOJ OCHENX DLINNOJ GLAVY, STOIT 
"OTSORTIROVATX" NAIBOLEE VAZHNYE FAKTY IZ CHISLA IZUCHENNYH.

aLGORITM SORTIROVKI---|TO PROCEDURA, KOTORAYA REORGANIZUET FAJL ZAPISEJ TAKIM 
OBRAZOM, CHTOBY KLYUCHI OKAZALISX V VOZRASTAYUSHCHEM PORYADKE. bLAGODARYA TAKOMU 
UPORYADOCHENNOMU RASPOLOZHENIYU GRUPPIRUYUTSYA ZAPISI S RAVNYMI KLYUCHAMI, 
STANOVITSYA VOZMOZHNOJ |FFEKTIVNAYA OBRABOTKA MNOGIH FAJLOV, 
OTSORTIROVANNYH PO ODNOMU KLYUCHU, SOZDAETSYA OSNOVA DLYA 
|FFEKTIVNYH ALGORITMOV VYBORKI I BOLEE UBEDITELXNO VYGLYADYAT DOKUMENTY,
 PODGOTOVLENNYE S POMOSHCHXYU evm.

\emph{vNUTRENNYAYA SORTIROVKA} ISPOLXZUETSYA V TEH SLUCHAYAH, KOGDA VSE ZAPISI 
POMESHCHAYUTSYA V BYSTROJ VNUTRENNEJ PAMYATI MASHINY. mY IZUCHILI S RAZNOJ 
STEPENXYU DETALIZACII BOLEE DVUH DESYATKOV ALGORITMOV VNUTRENNEJ SORTIROVKI, 
NO NAM, NAVERNOE, BYLO BY KUDA SPOKOJNEE, ESLI BY MY NE ZNALI TAK MNOGO 
RAZLICHNYH PODHODOV K |TOJ ZADACHE! iZUCHENIE VSEH |TIH METODOV BYLO PRIYATNYM 
VREMYAPROVOZHDENIEM. nO TEPERX PERED NAMI BEZRADOSTNAYA 
PERSPEKTIVA---PREDSTOIT NA DELE RESHITX, KAKOJ METOD SLEDUET ISPOLXZOVATX V 
TOJ ILI INOJ KONKRETNOJ SITUACII.

bYLO BY PREKRASNO, ESLI BY TOLXKO ODIN ILI DVA METODA SORTIROVKI 
PREVOSHODILI VSE OSTALXNYE BEZOTNOSITELXNO K PRILOZHENIYU ILI ISPOLXZUEMOJ 
MASHINE. nA SAMOM ZHE DELE KAZHDYJ METOD IMEET SVOI SOBSTVENNYE, ODNOMU EMU 
PRISUSHCHIE DOSTOINSTVA. nAPRIMER, METOD PUZYRXKA (ALGORITM~5.2.2v) NE IMEET 
YARKO VYRAZHENNYH PREIMUSHCHESTV, TAK KAK VSEGDA MOZHNO NAJTI LUCHSHIJ SPOSOB 
SDELATX TO, CHTO ON DELAET; NO DAZHE |TOT METOD POSLE SOOTVETSTVUYUSHCHEGO 
OBOBSHCHENIYA OKAZYVAETSYA POLEZNYM DLYA SORTIROVKI S DVUMYA LENTAMI (SM. 
P.~5.4.8). iTAK, PRIHODIM K ZAKLYUCHENIYU, CHTO POCHTI VSE ALGORITMY 
ZASLUZHIVAYUT TOGO, CHTOBY O NIH POMNILI, TAK KAK SUSHCHESTVUYUT PRILOZHENIYA, V 
KOTORYH ONI OKAZYVAYUTSYA VESXMA HOROSHIMI.

v SLEDUYUSHCHEM KRATKOM OBZORE OSVESHCHAYUTSYA OSNOVNYE ASPEKTY NAIBOLEE VAZHNYH 
ALGORITMOV VNUTRENNEJ SORTIROVKI, S KOTORYMI MY VSTRECHALISX. (kAK OBYCHNO,
 $N$ OZNACHAET CHISLO ZAPISEJ V FAJLE.)

%%452

1. {\sl rASPREDELYAYUSHCHIJ PODSCHET.\/} aLGORITM~5.2D OCHENX POLEZEN, ESLI 
DIAPAZON KLYUCHEJ NEVELIK. mETOD USTOJCHIV (NE IZMENYAETSYA PORYADOK ZAPISEJ S 
RAVNYMI KLYUCHAMI), NO TREBUETSYA PAMYATX DLYA SCHETCHIKOV I $2N$~ZAPISEJ. oDNA 
IZ MODIFIKACIJ, |KONOMYASHCHAYA $N$ IZ |TIH ZAPISEJ CENOJ USTOJCHIVOSTI, 
VSTRECHAETSYA V UPR. 5.2-13.

2. {\sl pROSTYE VSTAVKI.\/} aLGORITM 5.2.1S NAIBOLEE PROST 
DLYA PROGRAMMIROVANIYA, NE TREBUET DOPOLNITELXNOGO PROSTRANSTVA I VPOLNE 
|FFEKTIVEN PRI MALYH~$N$ (SKAZHEM, PRI $N\le 25$). pRI BOLXSHIH~$N$ ON 
STANOVITSYA NEVYNOSIMO MEDLENNYM, ESLI TOLXKO ISHODNYE DANNYE NE OKAZHUTSYA 
SRAZU POCHTI UPORYADOCHENNYMI.

3. {\sl sORTIROVKA S UBYVAYUSHCHIM SHAGOM.\/} aLGORITM 5.2.1D (METOD shELLA) TAK 
ZHE DOVOLXNO PROSTO PROGRAMMIRUETSYA, ISPOLXZUET MINIMALXNYJ OB®EM PAMYATI I 
DOVOLXNO |FFEKTIVEN PRI UMERENNO BOLXSHIH~$N$ (SKAZHEM, PRI $N\le 1000$).

4. {\sl vSTAVKI V SPISOK.\/} aLGORITM 5.2.1L OSNOVAN NA TOJ ZHE IDEE, CHTO I 
PROSTYE VSTAVKI, I PO|TOMU GODITSYA TOLXKO PRI NEBOLXSHIH~$N$. kAK I V 
DRUGIH METODAH SORTIROVKI SPISKOV, V NEM BLAGODARYA OPERACIYAM SO SSYLKAMI 
|KONOMITSYA STOIMOSTX PEREMESHCHENIYA DLINNYH ZAPISEJ; |TO OSOBENNO UDOBNO, 
KOGDA ZAPISI IMEYUT PEREMENNUYU DLINU ILI YAVLYAYUTSYA CHASTXYU DRUGIH STRUKTUR DANNYH.

5. {\sl sORTIROVKA S VYCHISLENIEM ADRESA\/} |FFEKTIVNA, ESLI KLYUCHI 
 PODCHINYAYUTSYA IZVESTNOMU (OBYCHNO RAVNOMERNOMU) ZAKONU RASPREDELENIYA; 
VAZHNEJSHIMI VARIANTAMI |TOGO PODHODA YAVLYAYUTSYA \emph{VSTAVKI V NESKOLXKO SPISKOV}
(ALGORITM 5.2.1m) I KOMBINIROVANNAYA PORAZRYADNAYA SORTIROVKA SO 
VSTAVKAMI mAKLARENA (RASSMOTRENNAYA V KONCE P.~5.2.5). dLYA POSLEDNEGO 
METODA DOSTATOCHNO IMETX $O(\sqrt{N})$ DOPOLNITELXNYH YACHEEK PAMYATI.

6. {\sl oBMENNAYA SORTIROVKA SO SLIYANIEM.\/} aLGORITM 5.2.2m (METOD 
b|TCHERA) I RODSTVENNYJ EMU ALGORITM \emph{BITONNOJ 
SORTIROVKI} (UPR.~5.3.4-10) POLEZNY, ESLI MOZHNO ODNOVREMENNO 
VYPOLNYATX BOLXSHOE CHISLO SRAVNENIJ.

7. {\sl oBMENNAYA SORTIROVKA S RAZDELENIEM\/} (METOD hOARA, 
SHIROKO IZVESTNYJ KAK \emph{BYSTRAYA SORTIROVKA}). aLGORITM 5.2.2Q, VEROYATNO,
 SAMYJ POLEZNYJ UNIVERSALXNYJ ALGORITM VNUTRENNEJ SORTIROVKI, POSKOLXKU 
ON TREBUET OCHENX MALO PAMYATI I OPEREZHAET SVOIH KONKURENTOV PO SREDNEMU 
VREMENI VYPOLNENIYA NA BOLXSHINSTVE VYCHISLITELXNYH MASHIN. oDNAKO V 
NAIHUDSHEM SLUCHAE ON MOZHET RABOTATX OCHENX MEDLENNO. pO|TOMU, ESLI 
VEROYATNOSTX NESLUCHAJNYH DANNYH DOSTATOCHNO VELIKA, PRIHODITSYA 
TSHCHATELXNO VYBIRATX RAZDELYAYUSHCHIJ |LEMENT. eSLI VYBIRAETSYA MEDIANA IZ TREH 
|LEMENTOV (KAK PREDLAGAETSYA V UPR. 5.2.2-55), TO TAKOE
%%453
POVEDENIE, KAK V NAIHUDSHEM SLUCHAE, STANOVITSYA KRAJNE MALOVEROYATNYM I, 
KROME TOGO, NESKOLXKO UMENXSHAETSYA SREDNEE VREMYA RABOTY.

8.~{\sl pROSTOJ VYBOR.\/} aLGORITM~5.2.3S DOVOLXNO PROST I OSOBENNO 
PODHODIT V SLUCHAE, KOGDA IMEETSYA SPECIALXNOE OBORUDOVANIE DLYA BYSTROGO 
POISKA NAIMENXSHEGO |LEMENTA V SPISKE.

9.~{\sl pIRAMIDALXNAYA SORTIROVKA.\/} aLGORITM~5.2.4n PRI MINIMALXNYH 
TREBOVANIYAH PAMYATI OBESPECHIVAET DOSTATOCHNO VYSOKUYU SKOROSTX SORTIROVKI; 
KAK SREDNEE VREMYA RABOTY, TAK I MAKSIMALXNOE VREMYA PRIMERNO VDVOE BOLXSHE 
SREDNEGO VREMENI BYSTROJ SORTIROVKI.

10.~{\sl  sLIYANIE SPISKOV.\/} aLGORITM~5.2.4L OSUSHCHESTVLYAET SORTIROVKU 
SPISKOV, PRI KOTOROJ, TAK ZHE KAK I PRI PIRAMIDALXNOJ SORTIROVKE, 
OBESPECHIVAETSYA VESXMA VYSOKAYA SKOROSTX DAZHE V NAIHUDSHEM SLUCHAE, KROME 
TOGO, |TOT METOD USTOJCHIV PO OTNOSHENIYU K RAVNYM KLYUCHAM.

11.~{\sl  pORAZRYADNAYA SORTIROVKA S ISPOLXZOVANIEM ALGORITMA\/} 5.2.5R---|TO 
NE CHTO INOE, KAK SORTIROVKA SPISKOV, KOTORAYA PRIEMLEMA DLYA KLYUCHEJ, LIBO 
OCHENX KOROTKIH, LIBO IMEYUSHCHIH NEOBYCHNYJ PORYADOK LEKSIKOGRAFICHESKOGO 
SRAVNENIYA. vMESTO SSYLOK MOZHNO PRIMENITX RASPREDELYAYUSHCHIJ PODSCHET 
(PUNKT~1 NASHEGO OBZORA); TAKAYA PROCEDURA POTREBUET PROSTRANSTVA DLYA 
$2N$~ZAPISEJ I DLYA TABLICY, SCHETCHIKOV, NO BLAGODARYA PROSTOTE VNUTRENNEGO 
CIKLA ONA OSOBENNO HOROSHA DLYA SVERHBYSTRYH evm---"POZHIRATELXNIC CHISEL", 
IMEYUSHCHIH OPEREZHAYUSHCHEE UPRAVLENIE. (\emph{pREDOSTEREZHENIE.} pORAZRYADNUYU 
SORTIROVKU NE SLEDUET ISPOLXZOVATX PRI MALYH~$N$.)

12.~{\sl  sORTIROVKA VSTAVKAMI I SLIYANIEM\/} (SM.~P.~5.3.1) 
NAIBOLEE PRIEMLEMA PRI OCHENX MALYH~$N$ V "PRYAMOLINEJNYH" 
PROGRAMMAH. nAPRIMER, |TOT METOD OKAZALSYA BY PODHODYASHCHIM V TEH 
PRILOZHENIYAH, GDE TREBUETSYA SORTIROVATX MNOGO GRUPP IZ PYATI ILI 
SHESTI ZAPISEJ.

13.  mOGUT SUSHCHESTVOVATX I GIBRIDNYE METODY, OB®EDINYAYUSHCHIE ODIN ILI BOLEE IZ 
PRIVEDENNYH VYSHE METODOV. nAPRIMER, KOROTKIE PODFAJLY, VOZNIKAYUSHCHIE PRI 
BYSTROJ SORTIROVKE, MOZHNO SORTIROVATX SLIYANIEM I VSTAVKAMI.

14. i NAKONEC, DLYA REALIZACII BEZYMYANNOGO METODA, VSTRETIVSHEGOSYA V 
OTVETE K UPR.~5.2.1-3, TREBUETSYA, PO-VIDIMOMU, KRATCHAJSHAYA IZ VOZMOZHNYH 
PROGRAMM SORTIROVKI. nO SREDNEE VREMYA RABOTY TAKOJ PROGRAMMY 
PROPORCIONALXNO~$N^3$, T.~E.~|TO SAMAYA MEDLENNAYA PROGRAMMA SORTIROVKI V KNIGE!

pROSTRANSTVENNYE I VREMENNYE HARAKTERISTIKI MNOGIH IZ |TIH METODOV, 
ZAPROGRAMMIROVANNYH DLYA \MIX, SVEDENY V TABL.~1.
%%454
\picture{tABLICA 1, STR. 454}
vAZHNO IMETX V VIDU, CHTO CHISLA V |TOJ TABLICE YAVLYAYUTSYA LISHX GRUBYMI 
POKAZATELYAMI OTNOSITELXNOGO VREMENI SORTIROVKI. oNI PRIMENIMY TOLXKO K 
ODNOJ evm, I PREDPOLOZHENIYA, KASAYUSHCHIESYA ISHODNYH DANNYH, DALEKO NE DLYA VSEH 
PROGRAMM ABSOLYUTNO PRAVOMERNY. sRAVNITELXNYE TABLICY, PODOBNYE |TOJ, 
PRIVODILISX VO MNOGIH RABOTAH, NO NE NAJDETSYA TAKIH DVUH AVTOROV,
 KOTORYE PRISHLI BY K ODINAKOVYM VYVODAM! tEM NE MENEE UKAZANIYA O VREMENI 
RABOTY POZVOLYAYUT OCENITX HOTYA BY PORYADOK SKOROSTI, KOTORUYU SLEDUET OZHIDATX 
OT KAZHDOGO ALGORITMA PRI SORTIROVKE ZAPISEJ IZ ODNOGO SLOVA, TAK KAK 
\MIX---DOVOLXNO TIPICHNAYA MASHINA.

sTOLBEC "PROSTRANSTVO" V TABL.~1 SODERZHIT NEKOTORUYU INFORMACIYU O 
KOLICHESTVE VSPOMOGATELXNOJ PAMYATI, ISPOLXZUEMOJ KAZHDYM ALGORITMOM, V 
EDINICAH DLINY ZAPISI. zDESX BUKVOJ~$\varepsilon$ OBOZNACHENA DOLYA ZAPISI, 
TREBUEMAYA DLYA ODNOGO POLYA SVYAZI; TAK, NAPRIMER, $N(1+\varepsilon)$ 
OZNACHAET, CHTO METOD TREBUET PROSTRANSTVO DLYA $N$~ZAPISEJ I $N$~POLEJ SVYAZI.

v ASIMPTOTICHESKIH SREDNIH I MAKSIMALXNYH VREMENAH, SODERZHASHCHIHSYA V 
TABL.~1, UCHITYVAYUTSYA TOLXKO GLAVNYE CHLENY, DOMINIRUYUSHCHIE PRI BOLXSHIH~$N$ V 
PREDPOLOZHENII SLUCHAJNYH ISHODNYH DANNYH; $c$~OBOZNACHAET PROIZVOLXNUYU 
KONSTANTU. eTI FORMULY MOGUT INOGDA VVESTI V ZABLUZHDENIE, PO|TOMU 
UKAZANO TAKZHE FAKTICHESKOE VREMYA RABOTY PROGRAMMY DLYA DVUH KONKRETNYH 
POSLEDOVATELXNOSTEJ ISHODNYH DANNYH. sLUCHAJ $N=16$, OTNOSITSYA K 
SHESTNADCATI KLYUCHAM, TAK CHASTO POYAVLYAVSHIMSYA V PRIMERAH \S~5.2, A SLUCHAJ 
$N=1000$ OTNOSITSYA K POSLEDOVATELXNOSTI $K_1$, $K_2$,~\dots, $K_{1000}$, 
OPREDELENNOJ FORMULAMI
$$
K_0=0; \quad K_{n+1}=(3141592621K_n+2113148651)\bmod 10^{10}.
$$
dLYA POLUCHENIYA HARAKTERISTIK KAZHDOGO ALGORITMA, PREDSTAVLENNOGO V TABLICE,
 ISPOLXZOVALASX VPOLNE "VYSOKOKACHESTVENNAYA" \MIX-PROGRAMMA, CHASTO S UCHETOM 
USOVERSHENSTVOVANIJ, PREDLOZHENNYH V UPRAZHNENIYAH. rAZMER BAJTA PRI 
VYPOLNENII |TIH PROGRAMM PRINYAT RAVNYM 100.

dLYA \emph{VNESHNEJ SORTIROVKI} NEOBHODIMY METODY, OTLICHAYUSHCHIESYA OT METODOV 
VNUTRENNEJ SORTIROVKI, POTOMU CHTO V |TOM SLUCHAE PREDPOLAGAETSYA 
ISPOLXZOVANIE SRAVNITELXNO PROSTYH STRUKTUR DANNYH I BOLXSHOE VNIMANIE 
UDELYAETSYA UMENXSHENIYU VREMENI VVODA/VYVODA. v P.~5.4.6 RASSMATRIVAYUTSYA 
INTERESNYE METODY, RAZVITYE DLYA LENTOCHNOJ SORTIROVKI, A V P.~5.4.9 
OBSUZHDAETSYA ISPOLXZOVANIE DISKOV I BARABANOV.

kONECHNO, SORTIROVKA---NE EDINSTVENNOE SODERZHANIE |TOJ GLAVY. pOPUTNO MY 
UZNALI MNOGO O TOM, KAK RABOTATX SO STRUKTURAMI DANNYH, KAK OBRASHCHATXSYA S 
VNESHNEJ PAMYATXYU I KAK ANALIZIROVATX ALGORITMY, I, NAVERNOE, MY UZNALI 
NEMNOZHKO I O TOM, KAK OTKRYVATX NOVYE ALGORITMY.
%%456

\section rANNIE RAZRABOTKI. pOISK ISTOCHNIKA SOVREMENNYH METODOV 
SORTIROVKI VOZVRASHCHAET NAS V 19-E~STOLETIE, KOGDA BYLI IZOBRETENY PERVYE 
MASHINY DLYA SORTIROVKI. v sOEDINENNYH shTATAH PEREPISX VSEH GRAZHDAN 
PROVODITSYA KAZHDYE 10~LET, I UZHE K 1880~G. PROBLEMA OBRABOTKI OGROMNYH PO 
OB®EMU DANNYH PEREPISI STALA OCHENX OSTROJ; I V SAMOM DELE, CHISLO ODINOKIH 
(V OTLICHIE OT CHISLA SOSTOYASHCHIH V BRAKE) V 1880~G. V TABLICAH OTSUTSTVUET, HOTYA
\picture{rIS. 94. tABULYATOR hOLLERITA. (fOTOGRAFIYA LYUBEZNO PREDOSTAVLENA 
ARHIVOM IBM.)
}
VSYA NEOBHODIMAYA, INFORMACIYA BYLA SOBRANA. gERMAN hOLLERIT, DVADCATILETNIJ 
SLUZHASHCHIJ bYURO PEREPISI, IZOBREL OSTROUMNYJ |LEKTRICHESKIJ TABULYATOR, 
OTVECHAYUSHCHIJ NUZHDAM SBORA STATISTIKI, I OKOLO 100 EGO MASHIN USPESHNO 
ISPOLXZOVALISX PRI OBRABOTKE SPISKOV PEREPISI 1890~G.

nA RIS.~94 IZOBRAZHEN PERVYJ APPARAT hOLLERITA, PRIVODIMYJ V DEJSTVIE OT 
AKKUMULYATORNYH BATAREJ. dLYA NAS OSNOVNOJ INTERES PREDSTAVLYAET 
"SORTIROVALXNYJ YASHCHIK" SPRAVA, KOTORYJ OTKRYT S  CELXYU POKAZATX POLOVINU IZ 
26 VNUTRENNIH OTDELENIJ. oPERATOR VSTAVLYAET PERFOKARTU RAZMERA 
$6{5\over8}\times3{1\over4}$~DYUJMOV V "PRESS" I OPUSKAET RUKOYATKU; |TO 
PRIVODIT K TOMU, CHTO ZAKREPLENNYE NA PRUZHINAH SHTYRI NA VERHNEJ PANELI V TEH
%%457
\bye