\input style
{ \catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}}
 \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}}
\htable{tABLICA 2}{"bYSTRAYA SORTIROVKA"}{
$\phantom{[}#\phantom{]}$\bskip&&$\phantom{[}#\phantom{]}$\bskip\cr
    &     &     &    &     &     &    &    &    &     &     &     &    &     &     &     & (l, r) & \hbox{sTEK}\cr
\noalign{\hrule}
[503& 087 & 512 & 061& 908 & 170 & 897& 275& 653& 426 & 154 & 509 & 612& 677 & 765 & 703]& (1,16) & - \cr
[154& 087 & 426 & 061& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (1,6)  & (8,16)\cr
[061& 087]& 154 &[426& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (1,2)  & (4,6)(8,16)\cr
 061& 087 & 154 &[426& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (4,6)  & (8,16)\cr
 061& 087 & 154 &[170& 275]& 426 & 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (4,5)  & (8, 16)\cr
 061& 087 & 154 & 170& 275 & 426 & 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (8,16) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[703& 653& 765 & 512 & 509 & 612& 677]& 897 & 908 & (8,14) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[677& 653& 612 & 512 & 509]& 703& 765 & 897 & 908 & (8,12) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[509& 653& 612 & 512]& 677 & 703& 765 & 897 & 908 & (8,11) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509&[653& 612 & 512]& 677 & 703& 765 & 897 & 908 & (9,11) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509&[512& 612]& 653 & 677 & 703& 765 & 897 & 908 & (9,10) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509& 512& 612 & 653 & 677 & 703& 765 & 897 & 908 &    -   & - \cr
\noalign{\hrule}
}}
tOLXKO CHTO OPISANNUYU PROCEDURU SORTIROVKI MOZHNO NAZVATX OBMENNOJ  
SORTIROVKOJ  \emph{S  RAZDELENIEM;} ONA  PRINADLEZHIT ch.~e.~r.~hOARU, 
INTERESNEJSHAYA STATXYA KOTOROGO 
[{\sl Comp. J.,\/} {\bf 5} (1962), 10--15]---ODNO IZ NAIBOLEE ISCHERPYVAYUSHCHIH 
IZ KOGDA-LIBO OPUBLIKOVANNYH SOOBSHCHENIJ OB |TOM METODE. hOAR OKRESTIL 
SVOJ METOD "quicksort" ("BYSTRAYA SORTIROVKA"), I |TO NAZVANIE 
VPOLNE SOOTVETSTVUET DEJSTVITELXNOSTI, TAK KAK, NAPRIMER, VESX PROCESS 
SORTIROVKI, POKAZANNYJ V TABL.~2, TREBUET VSEGO 48~SRAVNENIJ (MENXSHE 
LYUBOGO DRUGOGO VSTRECHAVSHEGOSYA UZHE METODA, ZA ISKLYUCHENIEM BINARNYH VSTAVOK, 
TREBUYUSHCHIH 47~SRAVNENIJ).
\picture{rIS ~19.  oBMENNAYA SORTIROVKA S RAZDELENIEM ("BYSTRAYA SORTIROVKA").}
vO VSEH SRAVNENIYAH NA DANNOJ STADII UCHASTVUET ODIN I GOT ZHE KLYUCH, TAK CHTO 
EGO MOZHNO HRANITX V REGISTRE. kROME TOGO, KOLICHESTVO PEREMESHCHENIJ DANNYH 
VESXMA UMERENNO: PRI VYCHISLENIYAH TABL.~2 PROIZVEDENO VSEGO $17$~OBMENOV, 
PRICHEM BOLXSHINSTVO IZ NIH---PROSTO "POLUOBMENY" (PROSTYE PERESYLKI), TAK KAK ODIN
%% 143
IZ KLYUCHEJ VSE VREMYA OSTAETSYA V REGISTRE, I EGO NE NUZHNO ZAPISYVATX DO 
SAMOGO KONCA STADII.

vSPOMOGATELXNYE OPERACII (TREBUEMYE DLYA UPRAVLENIYA STEKOM I 
PEREMENNYMI~$i$, $j$) NE SLOZHNY, NO IZ-ZA NIH PROCEDURA BYSTROJ SORTIROVKI 
POSREDSTVOM RAZDELENIJ PRIGODNA V OSNOVNOM DLYA BOLXSHIH ZNACHENIJ~$N$; 
PO|TOMU KOROTKIE PODFAJLY ZHELATELXNO SORTIROVATX OSOBOM OBRAZOM, KAK |TO 
DELAETSYA V SLEDUYUSHCHEM ALGORITME.

\alg Q.(oBMENNAYA SORTIROVKA S RAZDELENIEM.) zAPISI~$R_1$,~\dots, $R_N$ 
PERERAZMESHCHAYUTSYA NA TOM ZHE MESTE; POSLE ZAVERSHENIYA SORTIROVKI IH KLYUCHI 
BUDUT UPORYADOCHENY: $K_1\le\ldots\le K_N$. nUZHEN VSPOMOGATELXNYJ STEK DLYA 
HRANENIYA NE BOLEE CHEM $\log_2 N$~|LEMENTOV. eTOT ALGORITM SOOTVETSTVUET 
PROCEDURE "BYSTROJ SORTIROVKI" POSREDSTVOM RAZDELENIJ, PRIVEDENNOJ VYSHE, S 
NEBOLXSHIMI IZMENENIYAMI V CELYAH POVYSHENIYA |FFEKTIVNOSTI:
{\medskip\narrower
\item{a)}~pREDPOLAGAETSYA NALICHIE ISKUSSTVENNYH KLYUCHEJ~$K_0=-\infty$ 
I~$K_{N+1}=+\infty$, TAKIH, CHTO
$$
K_0\le K_i \le K_{N+1} \rem{PRI~$1\le i \le N$.}
\eqno (13)
$$
(rAVENSTVO DOPUSKAETSYA.)

\item{b)}~pODFAJLY, SOSTOYASHCHIE IZ~$M$ I MENEE |LEMENTOV, SORTIRUYUTSYA 
PROSTYMI VSTAVKAMI, GDE~$M\ge 1$---PARAMETR, KOTORYJ VYBIRAETSYA, KAK OPISANO NIZHE.

\item{c)}~nA NEKOTORYH STADIYAH DELAETSYA ODNO ILI DVA DOPOLNITELXNYH 
SRAVNENIYA (DOPUSKAETSYA PEREKRYTIE UKAZATELEJ~$i$, $j$), CHTOBY OSNOVNYE 
CIKLY SRAVNENIYA VYPOLNYALISX NASTOLXKO BYSTRO, NASKOLXKO |TO VOZMOZHNO.

\item{d)}~zAPISI S ODINAKOVYMI KLYUCHAMI MENYAYUTSYA MESTAMI, HOTYA |TO NE 
YAVLYAETSYA STROGO NEOBHODIMYM. (eTA IDEYA, PRINADLEZHASHCHAYA r.~k.~sINGLTONU, 
SPOSOBSTVUET RAZDELENIYU PODFAJLOV POCHTI POPOLAM, ESLI IMEYUTSYA RAVNYE 
KLYUCHI; SM.~UPR.~18.)
\medskip}

\st[nACHALXNAYA USTANOVKA.] oPUSTOSHITX STEK I USTANOVITX~$l\asg1$; $r\asg N$.

\st[nACHATX NOVUYU STADIYU.] (nAM HOTELOSX BY OTSORTIROVATX FAJL~$R_l$,~\dots,
$R_r$; IZ SAMOGO SUSHCHESTVA ALGORITMA VYTEKAET, CHTO~$r\ge l-1$, 
$K_{l-1}\le K_i \le K_{r+1}$ PRI~$l\le i \le r$.) eSLI~$r-l<M$, TO PEREJTI K 
SHAGU~\stp{8}. v PROTIVNOM SLUCHAE USTANOVITX~$i\asg l$, $j\asg r$, $K\asg K_l$, 
$R\asg R_l$. (oBSUZHDENIE NAILUCHSHEGO VYBORA~$R$ I~$K$ PRIVEDENO NIZHE.)

\st[sRAVNITX~$K:K_j$.] eSLI~$K<K_j$, TO UMENXSHITX~$j$ NA~$1$ I POVTORITX 
|TOT SHAG.

\st[pERESLATX~$R$ NA MESTO~$R_i$.] (k |TOMU MOMENTU $K_i$---KLYUCH~$\ge K$, 
NAHODYASHCHIJSYA NE NA SVOEM MESTE, I~$K\ge K_j$.) eSLI~$j\le i$, TO 
USTANOVITX~$R_i\asg R$ I PEREJTI K SHAGU~Q7. v PROTIVNOM SLUCHAE 
USTANOVITX~$R_i\asg R_j$ I UVELICHITX~$i$ NA~1.
%%144
\st[sRAVNITX~$K_i:K$.] eSLI~$K_i<K$, TO UVELICHITX~$i$ NA~$1$ I POVTORITX 
|TOT SHAG.

\st[pERESLATX~$R$ NA MESTO~$R_j$.] (k |TOMU MOMENTU $K_j$---KLYUCH~$\le K$, 
NAHODYASHCHIJSYA NE NA SVOEM MESTE, I~$K\le K_i$.) eSLI~$j\le i$, TO 
USTANOVITX~$R_j\asg R$ I~$i\asg j$. v PROTIVNOM SLUCHAE 
USTANOVITX~$R_j\asg R_i$,  UMENXSHITX~$j$ NA~$1$ I PEREJTI K SHAGU~\stp{3}.

\st[pOMESTITX V STEK.] (tEPERX PODFAJL~$R_l\ldots{}R_i\ldots{}R_r$ 
RAZDELEN TAK, CHTO~$K_k\le K_i$ PRI~$l\le k \le i$ I~$K_i\le K_k$ 
PRI~$i\le k \le r$ .) eSLI~$r-i\ge i-l$, TO POMESTITX V STEK~$(i+1, r)$ I 
USTANOVITX~$r\asg i-1$. v PROTIVNOM SLUCHAE POMESTITX V STEK~$(l, i-1)$ 
I USTANOVITX~$l\asg i+1$. (kAZHDYJ |LEMENT STEKA~$(a, b)$---|TO ZAYAVKA NA 
SORTIROVKU PODFAJLA~$R_a\ldots{}R_b$ V ODNOJ IZ POSLEDUYUSHCHIH STADIJ.) 
vERNUTXSYA K SHAGU~\stp{2}.

\st[sORTIROVKA PROSTYMI VSTAVKAMI.] dLYA~$j=l+1$, $l+2$,~\dots{} DO~$j>r$ 
VYPOLNYATX SLEDUYUSHCHIE OPERACII: USTANOVITX~$K\asg K_j$, $R\asg R_j$, $i\asg j-1$; 
ZATEM USTANOVITX~$R_{i+1}\asg R_i$, $i\asg i-1$ NULX ILI BOLEE RAZ 
DO TEH POR, POKA NE VYPOLNITSYA USLOVIE~$K_i\le K$; ZATEM 
USTANOVITX~$R_{i+1}\asg R$. (eTO, PO SUSHCHESTVU, ALGORITM~5.2.1S, 
PRIMENENNYJ K PODFAJLU IZ~$M$ ILI MENEE |LEMENTOV.)

\st[vZYATX IZ STEKA.] eSLI STEK PUST, TO SORTIROVKA ZAVERSHENA;
V PROTIVNOM SLUCHAE VZYATX VERHNIJ |LEMENT STEKA~$(l', r')$,
USTANOVITX~$l\asg l'$, $r\asg r'$ I VOZVRATITXSYA K SHAGU~\stp{2}.
\algend

sOOTVETSTVUYUSHCHAYA \MIX-PROGRAMMA DOVOLXNO VELIKA, NO NE SLOZHNA; NA SAMOM 
DELE BOLXSHAYA CHASTX KOMAND OTNOSITSYA K SHary~Q7, V KOTOROM PROVODYATSYA VESXMA 
PROSTYE MANIPULYACII S PEREMENNYMI.

\prog Q.(oBMENNAYA SORTIROVKA S RAZDELENIEM.) zAPISI, KOTORYE PREDSTOIT 
OTSORTIROVATX, NAHODYATSYA V YACHEJKAH $|INPUT|+1$,~\dots, $|INPUT|+N$; 
PREDPOLAGAETSYA, CHTO V YACHEJKAH~|INPUT| I~$|INPUT|+N+1$ SODERZHATSYA ZNACHENIYA, 
SOOTVETSTVENNO MINIMALXNO, I MAKSIMALXNO DOPUSTIMYE V MASHINE~\MIX. 
sTEK RASPOLAGAETSYA V YACHEJKAH $|STACK|+1$, $|STACK|+2$,~\dots; TOCHNOE CHISLO 
YACHEEK, KOTOROE NEOBHODIMO OTVESTI POD STEK, OBSUZHDAETSYA V UPR.~20. 
zNACHENIYA REGISTROV: $|rI1|\equiv l$, $|rI2|\equiv r$, $|rI3|\equiv i$, 
$|rI4|\equiv j$, $|rI6|\equiv \hbox{RAZMER STEKA}$, $|rA|\equiv K \equiv R$.
\code
A    & EQU  & 2:3       &      & pERVAYA KOMPONENTA |LEMENTA STEKA.
v    & EQU  & 4:5       &      & vTORAYA KOMPONENTA |LEMENTA STEKA.
START& ENT1 & 1         & 1    & Q1. nACHALXNAYA USTANOVKA. $l\asg1$.
     & ENT2 & N         & 1    & $r\asg N$.
     & ENT6 & 0         & 1    & oPUSTOSHITX STEK.
2H   & ENTX & 0,2       & 2A+1 & Q2. nACHATX NOVUYU STADIYU.
     & DECX & M,1       & 2A+1 & $|rX|\asg r-l-M$.
%%145
     & JXN  & 8F        & 2A+1 & k SHAGU~Q8, ESLI RAZMER PODFAJLA~$\le M$.
     & ENT3 & 0,1       & A    & $i\asg l$.
     & ENT4 & 0,2       & A    & $j\asg r$.
     & LDA  & INPUT,3   & A    & $K\asg K_i$.
     & JMP  & 3F        & A    & k SHAGU~Q3.
0H   & LDX  & INPUT,3   & B
     & STX  & INPUT,4   & B    & $R_j\asg R_i$.
     & DEC4 & 1         & C'-A & $j\asg j-1$.
3H   & CMPA & INPUT,4   & C'   & Q3.~sRAVNITX~$K:K_j$.
     & JL   & *-2       & C'   & eSLI~$<$, TO UMENXSHITX~$j$ I POVTORITX.
4H   & ENTX & 0,3       & B+A  & Q4.~pERESLATX~$R$ NA MESTO~$R_i$.
     & DECX & 0,4       & B+A
     & JXNN & 7F        & B+A  & k SHAGU~Q7, ESLI~$i\ge j$.
     & LDX  & INPUT,4   & B+X
     & STX  & INPUT,3   & B+X  & $R_i\asg R_j$.
     & INC3 & 1         & C''  & $i\asg i+1$.
5H   & smra & INPUT,3   & C''  & Q5.~sRAVNITX~$K_i:K$.
     & JG   & *-2       & C''  & eSLI~$<$, TO UVELICHITX~$i$ I POVTORITX.
6H   & ENTX & 0,3       & B+X  & Q6.~pERESLATX~$R$ NA MESTO~$R_i$.
     & DECX & 0,4       & B+X 
     & JXN  & 0B        & B+X  & k SHAGU~Q3, ESLI~$i<j$.
     & ENT3 & 0,4       & X    & $i\asg j$.
7H   & STA  & INPUT,3   & A    & Q7. pOMESTITX V STEK. $R_i\asg R$.
     & ENTA & 0,2       & A
     & DECA & 0,3       & A
     & DECA & 0,3       & A
     & INCA & 0,1       & A
     & INC6 & 1         & A    & $|rI6|\asg |rI6|+1$.
     & JANN & 1F        & A    & pEREHOD, ESLI~$r-i\ge i-l$.
     & ST1  & STACK,6(A)& A'
     & DEC3 & 1         & A'
     & ST3  & STACK,6(B)& A'   & $(l, i-1)\Rasg \hbox{STEK}$.
     & ENT1 & 2,3       & A'   & $l\asg i+1$.
     & JMP  & 2B        & A'   & k SHAGU~Q2.
1H   & INC3 & 1         & A-A'
     & ST3  & STACK,6(A)& A-A'
     & ST2  & STACK,6(B)& A-A' & $(i+1, r)\Rasg\hbox{STEK}$.
     & ENT2 & -2,3      & A-A' & $r\asg i-1$.
     & JMP  & 2B        & A-A' & k SHAGU~Q2.
8H   & DEC2 & 0,1       & A+1  & Q8. sORTIROVKA PROSTYMI VSTAVKAMI.
     & J2NP & 9F        & A+1  & k SHAGU~Q9, ESLI~$r\le l$.
     & ENT4 & 1,1       & A+1-L& $j\asg l+1$.
1H   & LDA  & INPUT,4   & D    & $R\asg R_j$.
     & ENT3 & -1,4      & D    & $i\asg j-1$.
     & JMP  & *+4       & D    & pEREHOD I CIKL.
     & LDX  & INPUT,3   & E
     & STX  & INPUT+1,3 & E    & $R_{i+1}\asg R_i$.
     & DEC3 & 1         & E    & $i\asg i-1$.
     & smra & INPUT,3   & D+E
     & JL   & *-4       & D+E  & pEREHOD, ESLI~$K<K_i$.
     & STA  & INPUT+1,3 & D    & $R_{i+1}\asg R$.
%% 146
     & INC4 & 1         & D    & $j\asg j+1$.
     & DEC2 & 1         & D
     & J2P  & 1B        & D    & pOVTORITX $r-l$~RAZ.
9H   & LD1  & STACK,6(A)& A+1  & Q9. vZYATX IZ STEKA.
     & LD2  & STACK,6(B)& A+1  & $(l, r)\Asg\hbox{STEK}$.
     & DEC6 & 1         & A+1  & $|rI6|\asg|rI6|-1$.
     & J6NN & 2B        & A+1  & k SHAGU~Q2, ESLI STEK NE BYL PUST.
\endcode
\progend
\section aNALIZ "BYSTROJ SORTIROVKI". iNFORMACIYU O VREMENI VYPOLNENIYA, 
PRIVEDENNUYU VMESTE S PROGRAMMOJ~Q, NETRUDNO VYVESTI IZ ZAKONA kIRHGOFA, 
ILI ZAKONA SOHRANENIYA (SM.~P.~1.3.3), I IZ TOGO FAKTA, CHTO VSE POMESHCHENNOE 
V STEK V KONCE KONCOV OTTUDA IZVLEKAETSYA. oBSHCHEE VREMYA RABOTY ZAVISIT OT 
SLEDUYUSHCHIH VELICHIN:
$$
\eqalign{
  A&=\hbox{CHISLO STADIJ, NA KOTORYH DANNYJ PODFAJL SODERZHIT BOLEE $M$~|LEMENTOV;}\cr
  B&=\hbox{CHISLO PRISVAIVANIJ~$R_j\asg R_i$ V SHAGE~Q6;}\cr
 C'&=\hbox{CHISLO VYPOLNENIJ SHAGA~Q3;}\cr
C''&=\hbox{CHISLO VYPOLNENIJ SHAGA~Q5;}\cr
  D&=\hbox{CHISLO PRISVAIVANIJ~$R\asg R_j$ V SHAGE~Q8;}\cr
  E&=\hbox{CHISLO PRISVAIVANIJ~$R_{i+1}\asg R_i$ V SHAGE~Q8;}\cr
  L&=\hbox{CHISLO SLUCHAEV, KOGDA V SHAGE~Q8 $r\le l$;}\cr
  X&=\hbox{CHISLO OPERACIJ~$i\asg j$ V SHAGE Q6.}\cr
}
\eqno(14)
$$
mY NE BUDEM ANALIZIROVATX VELICHINY~$C'$ I~$C''$ NEZAVISIMO, A RASSMOTRIM LISHX
$$
C=C'+C''=\hbox{OBSHCHEE CHISLO SRAVNENIJ},
\eqno(15)
$$
TAK KAK VREMYA RABOTY DLYA~$C'$ I~$C''$ ODINAKOVO. iZUCHIV SEMX VELICHIN: 
$A$, $B$, $C$, $D$, $E$, $L$ I~$X$, MY SMOZHEM RAZUMNO VYBRATX PARAMETR~$M$,
KOTORYM OPREDELYAETSYA "POROG" MEZHDU SORTIROVKOJ PROSTYMI VSTAVKAMI I 
RAZDELENIEM. (eSLI CHITATELX NE MATEMATIK, ON MOZHET PROPUSTITX VSE VPLOTX 
DO FORMUL~(25).)

kAK I PRI ANALIZE BOLXSHINSTVA DRUGIH ALGORITMOV V |TOJ GLAVE, MY BUDEM 
PREDPOLAGATX, CHTO SORTIRUEMYE KLYUCHI RAZLICHNY;. V UPR.~18 POKAZANO, CHTO 
NALICHIE RAVNYH KLYUCHEJ NE SNIZHAET SUSHCHESTVENNO |FFEKTIVNOSTI ALGORITMA~Q; 
V DEJSTVITELXNOSTI PRISUTSTVIE RAVNYH KLYUCHEJ, PO-VIDIMOMU, DAZHE 
SPOSOBSTVUET EE UVELICHENIYU. tAK KAK METOD ZAVISIT TOLXKO OT 
OTNOSITELXNOGO RASPOLOZHENIYA KLYUCHEJ, TO MOZHNO PREDPOLAGATX TAKZHE, CHTO 
|TO PROSTO CHISLA~$\set{1, 2,~\ldots, N}$, RASPOLOZHENNYE V NEKOTOROM PORYADKE.

kOGDA MY VPERVYE DOSTIGAEM SHAGA~Q2, SORTIROVKA SVODITSYA K PROSTYM VSTAVKAM,
ESLI~$N\le M$, A |TO MY UZHE IZUCHILI; PO|TOMU PREDPOLOZHIM, CHTO~$N>M$. 
nEOBHODIMO LISHX RAZOBRATXSYA V VYCHISLENIYAH, KOTORYE V PERVYJ RAZ PRIVODYAT K SHAGU~Q7;
%% 147
NETRUDNO VIDETX, CHTO PRI RAZDELENII ZAPISI V OBOIH 
PODFAJLAH $R_1\ldots{}R_{i-1}$ I~$R_{i+1}\ldots{}R_N$ BUDUT RASPOLOZHENY V 
SLUCHAJNOM PORYADKE, ESLI TOLXKO ZAPISI ISHODNOGO FAJLA BYLI RASPOLOZHENY V 
SLUCHAJNOM PORYADKE. zNACHIT, VKLAD POSLEDUYUSHCHIH VYCHISLENIJ MOZHNO OPREDELITX, 
PRIMENIV INDUKCIYU PO~$N$.

pUSTX~$s$---ZNACHENIE PERVOGO KLYUCHA~$K_1$, I PREDPOLOZHIM, CHTO ROVNO~$t$ IZ 
KLYUCHEJ~$K_1$,~\dots, $K_s$ PREVOSHODYAT~$s$. pUSTX
$$
h=\cases{
1, & ESLI~$K_s<s$; \cr
0, & ESLI~$K_s\ge s$.
}
\eqno(16)
$$
iNACHE GOVORYA, $h=1$, ESLI KLYUCH, KOTORYJ VNACHALE ZANIMAL POZICIYU~$s$ 
(KUDA POPADET KLYUCH~$K_1$), BUDET PEREMESHCHEN VLEVO. nAPOMNIM, CHTO 
SORTIRUEMYE KLYUCHI YAVLYAYUTSYA CELYMI CHISLAMI IZ MNOZHESTVA~$\set{1, 2,~\ldots, N}$.

eSLI~$s=1$, TO NETRUDNO VIDETX, CHTO PROIZOJDET VO VREMYA PERVOJ STADII 
RAZDELENIYA. shAG~Q3 VYPOLNITSYA $N$~RAZ, POSLE CHEGO SHAG~Q4 PRIVEDET NAS K~Q7.
tAKIM OBRAZOM, PERVAYA STADIYA V |TOM SLUCHAE DAST TAKIE VKLADY: $A=1$, 
$B=0$, $C=N$, $X=0$. aNALOGICHNYE, NO NESKOLXKO BOLEE SLOZHNYE RASSUZHDENIYA 
DLYA SLUCHAYA~$s>1$ (SM.~UPR.~21) POKAZYVAYUT, CHTO VKLADAMI PERVOJ STADII V 
SUMMARNOE VREMYA VYPOLNENIYA V OBSHCHEM SLUCHAE BUDUT
$$
A=1,\quad B=t, \quad C=N+1-\delta_{s1},\quad X=h \rem{PRI~$1<s\le N$.}
\eqno(17)
$$
k |TOMU NEOBHODIMO DOBAVITX VKLADY DOSLEDUYUSHCHIH STADIJ, VO VREMYA KOTORYH 
UPORYADOCHIVAYUTSYA PODFAJLY SOOTVETSTVENNO IZ~$s-1$ I~$N-S$~|LEMENTOV.

eSLI PREDPOLOZHITX, CHTO V ISHODNOM FAJLE ZAPISI RASPOLAGALISX V SLUCHAJNOM 
PORYADKE, TO MOZHNO VYPISATX FORMULY, KOTORYMI OPREDELYAYUTSYA PROIZVODYASHCHIE 
FUNKCII DLYA RASPREDELENIJ VEROYATNOSTEJ VELICHIN~$A$, $B$,~\dots, $X$ 
(SM.~UPR.~22). nO DLYA PROSTOTY MY IZUCHIM ZDESX TOLXKO \emph{SREDNIE 
ZNACHENIYA} |TIH VELICHIN~$A_N$, $B_N$,~\dots, $X_N$ KAK FUNKCII OT~$N$. 
rASSMOTRIM, NAPRIMER, SREDNEE CHISLO SRAVNENIJ~$C_N$, VYPOLNENNYH V 
PROCESSE RAZDELENIYA. eSLI~$N\le M$, TO~$C_N=0$. pRI~$N>M$, TAK KAK LYUBOE 
DANNOE ZNACHENIE~$s$ VSTRECHAETSYA S VEROYATNOSTXYU~$1/N$,
$$
\eqalignno{
C_N&={1\over N}\sum_{1\le s \le N} (N+1-\delta_{s1}+C_{s-1}+C_{N-s})=\cr
   &=N+1-{1\over N}+{2\over N}\sum_{0\le k < N} C_k. & (18) \cr
}
$$
aNALOGICHNYE FORMULY IMEYUT MESTO I DLYA OSTALXNYH VELICHIN~$A_N$, $B_N$,~\dots, 
$X_N$ (SM.~UPR.~23).
%% 148

sUSHCHESTVUET PROSTOJ SPOSOB RESHENIYA REKURRENTNYH SOOTNOSHENIJ VIDA
$$
x_n=f_n+{2\over n}\sum_{0\le k < n} x_k \rem{PRI $n\ge m$.}
\eqno(19)
$$
nA PERVOM SHAGE OSVOBOZHDAYUTSYA OT ZNAKA SUMMIROVANIYA: POSKOLXKU
$$
\eqalign{
(n+1)x_{n+1}&=(n+1)f_{n+1}+2\sum_{0\le k \le n} x_k, \cr
      n x_n &=nf_n+2\sum_{0\le k<n} x_k,\cr
}
$$
TO MOZHNO VYCHESTX VTOROE RAVENSTVO IZ PERVOGO, POLUCHIV
$$
(n+1)x_{n+1}-nx_n=g_n+2x_n, \rem{GDE $g_n=(n+1)f_{n+1}-nf_n$.}
$$
tEPERX REKURRENTNAYA ZAVISIMOSTX PRINIMAET GORAZDO BOLEE PROSTOJ VID:
$$
(n+1)x_{n+1}=(n+2)x_n+g_n \rem{PRI $n\ge m$.}
\eqno(20)
$$
\emph{lYUBOE} REKURRENTNOE SOOTNOSHENIE OBSHCHEGO VIDA
$$
a_n x_{n+1}=b_n x_n + g_n
\eqno(21)
$$
MOZHNO SVESTI K PROSTOJ SUMME, ESLI UMNOZHITX OBE CHASTI NA SUMMIRUYUSHCHIJ 
MNOZHITELX~$a_0a_1\ldots{}a_{n-1}/b_0b_1\ldots{}b_n$. pOLUCHAEM
$$
y_{n+1}=y_n+c_n, 
\rem{GDE $\displaystyle y_n={a_0\ldots a_{n-1}\over b_0\ldots b_{n-1}}x_n$,
$\displaystyle c_n={a_0\ldots a_{n-1}\over b_0\ldots b_n}g_n$.}
\eqno(22)
$$
v SLUCHAE~(20) SUMMIRUYUSHCHIJ MNOZHITELX RAVEN PROSTO~$n!/(n+2)!=1/(n+1)(n+2)$. 
tAKIM OBRAZOM, NAHODIM, CHTO PROSTOE SOOTNOSHENIE
$$
{x_{n+1}\over n+2}={x_n \over n+1}+{(n+1)f_{n+1}-nf_n \over (n+1)(n+2)},
\rem{$n\ge m$,}
\eqno(23)
$$
YAVLYAETSYA SLEDSTVIEM SOOTNOSHENIYA~(19).

eSLI, NAPRIMER, POLOZHITX~$f_n=1/n$, TO POLUCHITSYA NEOZHIDANNYJ 
REZULXTAT~$x_n/(n+1)=x_m/(m+1)$ PRI LYUBOM~$n\ge m$. 
eSLI POLOZHITX~$f_n=n+1$, TO POLUCHITSYA
$$
\eqalign{
x_n/(n+1)&=2/(n+1)+2/n+\cdots+2/(m+2)+x_m/(m+1)=\cr
         &=2(H_{n+1}-H_{m+1})+x_m/(m+1)\cr
}
$$
PRI LYUBOM~$n\ge m$. kOMBINACIYA |TIH DVUH RESHENIJ I PODSTANOVKA~$m=M+1$ 
I~$x_n=0$ PRI~$n\le M$ DAYUT FORMULU
$$
\eqalignno{
C_N&=(N+1)\left(2H_{N+1}-2H_{M+2}+1-{1\over (M+1)(M+2)}\right)\approx\cr
&\approx 2(N+1)\ln \left({N+1\over M+2}\right) \rem{PRI~$N>M$.} &(24)\cr
}
$$
%% 149
v P.~6.2.2 MY DOKAZHEM, CHTO STANDARTNOE OTKLONENIE 
VELICHINY~$C_N$ ASIMPTOTICHESKI RAVNO~$\sqrt{(21-2\pi^2)}/3N$; |TO DOVOLXNO 
MALO PO SRAVNENIYU S~(24).

oSTALXNYE VELICHINY MOZHNO NAJTI ANALOGICHNYM SPOSOBOM (SM.~UPR.~23); IMEEM
$$
\eqalign{
A_N&=2(N+1)/(M+2)-1,\cr
B_N&={1\over 6}(N+1)\left(2H_{N+1}-2H_{M+2}+1-{6\over M+2}\right)+{1\over2},\cr
D_N&=(N+1)M(M-1)/(M+2)(M+1),\cr
E_N&={1\over6}(N+1)M(M-1)/(M+2),\cr
L_N&=4(N+1)/(M+2)(M+1),\cr
X_N&=(N+1)/(M+2)-{1\over2} \rem{PRI $N>M$.}\cr
}
\eqno(25)
$$

pRIVEDENNOE VYSHE OBSUZHDENIE POKAZYVAET, CHTO MOZHNO PROIZVESTI TOCHNYJ 
ANALIZ SREDNEGO VREMENI VYPOLNENIYA VESXMA SLOZHNOJ PROGRAMMY, ISPOLXZUYA 
METODY, KOTORYE MY RANEE PRIMENYALI LISHX K BOLEE PROSTYM SLUCHAYAM.

chTOBY OPREDELITX "NAILUCHSHEE" ZNACHENIE~$M$ DLYA KONKRETNOJ MASHINY, MOZHNO 
VOSPOLXZOVATXSYA FORMULAMI~(24) I~(25). pROGRAMMA~Q DLYA MASHINY~\MIX{} 
TREBUET $37A+14B+4C+12D+8E-L+8X+15$~EDINIC VREMENI; |TO RAVNO V SREDNEM
${1\over3}(38(N+1)H_N+(N+1)f(M))-19$~EDINIC PRI~$N>M$, GDE
$$
f(M)=4M+38H_{M+2}+43+{84\over M+2}+{48\over (M+2)(M+1)}.
\eqno(26)
$$
mY HOTIM VYBRATX TAKOE ZNACHENIE~$M$, PRI KOTOROM FUNKCIYA~$f(M)$ DOSTIGAET 
MINIMUMA. v DANNOM SLUCHAE
$$
f(M)-f(M-1)=4-{38\over M+2}-{84\over (M+2)(M+1)}-{96 \over(M+2)(M+1)M},
$$
I TREBUETSYA NAJTI TAKOE ZNACHENIE~$M$, CHTOBY~$f(M)-f(M-1)\le 0$,
$f(M+1)-f(M)\ge 0$; RESHENIE~$M=9$ NAJTI NETRUDNO. eSLI~$M=9$, TO PRI 
BOLXSHIH~$N$ SREDNEE VREMYA VYPOLNENIYA PROGRAMMY~Q RAVNO 
PRIBLIZITELXNO~$12.67(N+1)\ln N-1.92N-14.59$.

tAKIM OBRAZOM, PROGRAMMA~Q RABOTAET V SREDNEM DOVOLXNO BYSTRO; SLEDUET, 
KROME TOGO, UCHESTX, CHTO ONA TREBUET OCHENX MALO PAMYATI. nO KAKOV 
\emph{NAIHUDSHIJ} SLUCHAJ DLYA ALGORITMA~Q? sUSHCHESTVUYUT LI KAKIE-NIBUDX 
ISHODNYE FAJLY, OBRABATYVATX KOTORYE |TIM ALGORITMOM NE |FFEKTIVNO? oTVET 
NESKOLXKO OBESKURAZHIVAET: ESLI ISHODNYJ FAJL UZHE UPORYADOCHEN, A 
IMENNO~$K_1<K_2<\ldots<K_N$, TO KAZHDAYA OPERACIYA "RAZDELENIYA" STANOVITSYA 
POCHTI BESPOLEZNOJ, TAK KAK PODFAJL SVODITSYA K ODNOMU |LEMENTU! zNACHIT, V 
|TOJ SITUACII (KOTORAYA DOLZHNA BYTX SAMOJ PROSTOJ
%% 150
\bye