\input style %% 188 pUSTX $s_l$---RAZMER PODDEREVA S KORNEM~$l$, A~$M_N$---MULXTIMNOZHESTVO~$\{s_1, s_2, \ldots, s_N\}$ VSEH |TIH RAZMEROV. iSPOLXZUYA (14) I (15), LEGKO VYCHISLITX~$M_N$ PRI LYUBOM ZADANNOM~$N$. v UPR.~5.1.4--20 POKAZANO, CHTO OBSHCHEE CHISLO SPOSOBOV POSTROITX PIRAMIDU IZ CELYH CHISEL $\{1, 2, \ldots, N\}$ RAVNO $$ N!/s_1s_2\ldots s_N= N!/\prod_{s\in M_N} s. \eqno(16) $$ nAPRIMER, CHISLO SPOSOBOV RASPOLOZHITX 26 BUKV $\{A, B, C, \ldots, Z\}$ NA RIS.~28 TAK, CHTOBY PO VERTIKALI SOHRANYALSYA ALFAVITNYJ PORYADOK, RAVNO $$ 26!/(26 \cdot 10 \cdot 6 \cdot 2 \cdot 1 \cdot 1^{12} \cdot 3^6 \cdot 7^2 \cdot 15^1). $$ tEPERX MY V SOSTOYANII PROANALIZIROVATX FAZU POSTROENIYA PIRAMIDY V ALGORITME~H, T. E. VYCHISLENIYA, KOTORYE ZAVERSHAYUTSYA DO TOGO, KAK V SHAGE H2 VPERVYE VYPOLNITSYA USLOVIE $l=1$. k SCHASTXYU, BLAGODARYA SLEDUYUSHCHEJ NIZHE TEOREME ANALIZ POSTROENIYA PIRAMIDY MOZHNO SVESTI K IZUCHENIYU NEZAVISIMYH OPERACIJ PROTASKIVANIYA. \proclaim tEOREMA H. eSLI ISHODNYMI DANNYMI DLYA ALGORITMA H SLUZHIT SLUCHAJNAYA PERESTANOVKA MNOZHESTVA $\{ 1, 2, \ldots, N\}$, TO V FAZE POSTROENIYA PIRAMIDY S ODINAKOVOJ VEROYATNOSTXYU MOZHET POLUCHITXSYA LYUBAYA IZ $N! /\left(\prod_{s\in M_N} s\right)$ VOZMOZHNYH PIRAMID. bOLEE moGO, VSE $\floor{N/2}$ OPERACIJ PROTASKIVANIYA, VYPOLNENNYE ZA VREMYA |TOJ FAZY, "RAVNOMERNY" V TOM SMYSLE, CHTO PO DOSTIZHENII SHAGA H8 VSE $s_l$ VOZMOZHNYH ZNACHENIJ PEREMENNOJ~$i$ RAVNOVEROYATNY. \proof pRIMENIM METOD, KOTORYJ V CHISLENNOM ANALIZE NAZYVAETSYA METODOM "OBRATNOJ ZADACHI". pUSTX V KACHESTVE ODNOGO IZ VOZMOZHNYH REZULXTATOV OPERACII PROTASKIVANIYA ZADANA PIRAMIDA $K_1$ \dots{} $K_N$ S KORNEM V UZLE~$l$; TOGDA YASNO, CHTO IMEETSYA VSEGO~$s_l$ ISHODNYH KONFIGURACIJ $K'_1$ \dots{} $K'_N$ FAJLA, KOTORYE POSLE PROTASKIVANIYA DAYUT TAKOJ REZULXTAT. vSE |TI ISHODNYE KONFIGURACII IMEYUT RAZLICHNYE ZNACHENIYA $K'_l$, SLEDOVATELXNO, RASSUZHDAYA V OBRATNOM NAPRAVLENII, SUSHCHESTVUET ROVNO $s_l$ $s_{l+1}$ \dots{} $s_N$ ISHODNYH PERESTANOVOK MNOZHESTVA $\{1, 2, \ldots, N\}$, KOTORYE POSLE ZAVERSHENIYA OPERACII PROTASKIVANIYA V POZICIYU~$l$ DAYUT KONFIGURACIYU $K_1$ \dots{} $K_N$. sLUCHAJ $l=1$ TIPICHEN: PUSTX $K_1$ \dots{} $K_N$---PIRAMIDA, I PUSTX $K'_1$ \dots{} $K'_N$---FAJL, KOTORYJ PREOBRAZUETSYA V $K_1$ \dots{} $K_N$ V REZULXTATE PROTASKIVANIYA PRI $l=1$, $K=K'_1$. eSLI $K=K_i$, TO DOLZHNY IMETX MESTO RAVENSTVA $K'_i=K_{\floor{i/2}}$, $K'_{\floor{i/2}}=K_{\floor{i/4}}$ I T. D., PRI |TOM $K'_j=K_j$ DLYA VSEH $j$, NE LEZHASHCHIH NA PUTI OT~$1$ K~$i$. oBRATNO, PRI LYUBOM~$i$ V REZULXTATE TAKOGO POSTROENIYA POLUCHAETSYA FAJL $K'_1$ \dots{} $K'_N$, TAKOJ, CHTO (a) OPERACIYA PROTASKIVANIYA PREOBRAZUET %% 189 FAJL $K'_1$ \dots{} $K'_N$ V $K_1$ \dots{} $K_N$ I (b) $K_{\floor{j/2}}\ge K_j$ PRI $2 \le \floor{j/2}r$. pOKAZHITE, CHTO ESLI $K\ge K_{r+1}$, TO MOZHNO BYLO BY TAK UPROSTITX SHAG~H4, CHTOBY RAZVETVLENIE PROISHODILO LISHX PO DVUM PUTYAM. kAK NADO IZMENITX SHAG~H2, CHTOBY OBESPECHITX V PROCESSE PIRAMIDALXNOJ SORTIROVKI VYPOLNENIE USLOVIYA $K\ge K_{r+1}$? \ex[10] pOKAZHITE, CHTO PROSTAYA OCHEREDX---CHASTNYJ SLUCHAJ PRIORITETNOJ. (oB®YASNITE, KAKIE KLYUCHI NUZHNO PRISVAIVATX |LEMENTAM, CHTOBY PROCEDURA "NAIBOLXSHIJ IZ VKLYUCHENNYH---PERVYM ISKLYUCHAETSYA" BYLA |KVIVALENTNA PROCEDURE "PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA".) yaVLYAETSYA LI STEK TAKZHE CHASTNYM SLUCHAEM PRIORITETNOJ OCHEREDI? \rex[M22] (v.~e.~chARTRS.) pRIDUMAJTE BYSTRYJ ALGORITM POSTROENIYA TABLICY PROSTYH CHISEL $\le N$, V KOTOROM ISPOLXZUETSYA \emph{PRIORITETNAYA OCHEREDX} S CELXYU IZBEZHATX OPERACIJ DELENIYA. [\emph{uKAZANIE.} pUSTX NAIMENXSHIJ KLYUYA V PRIORITETNOJ OCHEREDI BUDET NAIMENXSHIM NECHETNYM NEPROSTYM CHISLOM, BOLXSHIM, CHEM SAMOE POSLEDNEE NECHETNOE CHISLO, VOSPRINYATOE KAK KANDIDAT V PROSTYE CHISLA. pOPYTAJTESX SVESTI K MINIMUMU CHISLO |LEMENTOV V |TOJ OCHEREDI.] \ex[20] pOSTROJTE |FFEKTIVNYJ ALGORITM, KOTORYJ VSTAVLYAET NOVYJ KLYUCH V DANNUYU PIRAMIDU IZ P |LEMENTOV, POROZHDAYA PIRAMIDU IZ $n+1$~|LEMENTOV. \ex[20] aLGORITM IZ UPR.~16 MOZHNO ISPOLXZOVATX DLYA POSTROENIYA PIRAMIDY VZAMEN METODA "UMENXSHENIYA $l$ DO~$1$", PRIMENYAEMOGO V ALGORITME~H. %%192 pOROZHDAYUT LI OBA METODA IZ ODNOGO I TOGO ZHE ISHODNOGO FAJLA ODNU I TU ZHE PIRAMIDU? \rex[21] (r.~u.~fLOJD) vO VREMYA FAZY VYBORA V ALGORITME PIRAMIDALXNOJ SORTIROVKI KLYUCH $K$, KAK PRAVILO, PRINIMAET DOVOLXNO MALYE ZNACHENIYA, I PO|TOMU POCHTI PRI VSEH SRAVNENIYAH V SHAGE H6 OBNARUZHIVAETSYA, CHTO $KK_j$, PEREJTI K SHAGU~\stp{8}. eSLI $i=j$, USTANOVITX $P_k\asg R_i$ I PEREJTI K SHAGU \stp{13}. \st[pERESYLKA $R_i$.] (shAGI \stp{4}--\stp{7} ANALOGICHNY SHAGAM M3--M4 ALGORITMA~M.) uSTANOVITX $R_k\asg R_i$, $k\asg k+d$. \st[sTUPENXKA VNIZ?] uVELICHITX $i$ NA~1. zATEM, ESLI $K_{i-1}\le K_i$, VOZVRATITXSYA K SHAGU \stp{3}. \st [pERESYLKA $R_j$.] uSTANOVITX $R_k\asg R_j$, $k\asg k+d$. \st[sTUPENXKA VNIZ?] uMENXSHITX $j$ NA~1. zATEM, ESLI $K_{j+1}\le K_j$, VOZVRATITXSYA K SHAGU \stp{6}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{12}. %% 197 \st[pERESYLKA $R_j$.] (shAGI \stp{8}--\stp{11} DVOJSTVENNY PO OTNOSHENIYU K SHAGAM~\stp{4}--\stp{7}.) uSTANOVITX $R_k\asg R_j$, $k\asg k+d$. \st[sTUPENXKA VNIZ?] uMENXSHITX $j$ NA 1. zATEM, ESLI $K_{j+1}\le K_j$, VOZVRATITXSYA K SHAGU \stp{3}. \st[pERESYLKA $R_i$.] uSTANOVITX~$R_k\asg R_i$, $k\asg k+d$. \st[sTUPENXKA VNIZ?] uVELICHITX $i$ NA~$1$. zATEM, ESLI $K_{i-1}\le K_i$, VOZVRATITXSYA K SHAGU \stp{10}. \st[pEREKLYUCHENIE NAPRAVLENIYA.] uSTANOVITX $f\asg0$, $d\asg-d$ I VZAIMOZAMENITX $k\xchg l$. vOZVRATITXSYA K SHAGU \stp{3}. \st[pEREKLYUCHENIE OBLASTEJ.] eSLI $f=0$, TO USTANOVITX $s\asg 1-s$ I VOZVRATITXSYA K~\stp{2}. v PROTIVNOM SLUCHAE SORTIROVKA ZAVERSHENA; ESLI $s=0$, TO USTANOVITX $(R_1,~\ldots, R_N)\asg(R_{N+1}, \ldots, R_{2N})$. (eSLI REZULXTAT MOZHNO OSTAVITX V OBLASTI~$(R_{N+1}, \ldots, R_{2N})$, TO POSLEDNEE KOPIROVANIE NEOBYAZATELXNO.) \algend v |TOM ALGORITME ESTX ODNA NEBOLXSHAYA TONKOSTX, KOTORAYA OB®YASNYAETSYA V UPR.~5. zAPROGRAMMIROVATX ALGORITM~N DLYA MASHINY~\MIX\ NETRUDNO, NO OSNOVNYE SVEDENIYA O EGO POVEDENII MOZHNO POLUCHITX I BEZ POSTROENIYA VSEJ PROGRAMMY. eSLI FAJL SLUCHAEV, TO V NEM OKOLO ${1\over2}N$ VOZRASTAYUSHCHIH OTREZKOV, TAK KAK $K_i>K_{i+1}$ S VEROYATNOSTXYU~$1\over2$; PODROBNAYA INFORMACIYA O CHISLE OTREZKOV PRI NESKOLXKO OTLICHNYH PREDPOLOZHENIYAH BYLA POLUCHENA V P.~5.1.3. pRI KAZHDOM PROSMOTRE CHISLO OTREZKOV SOKRASHCHAETSYA VDVOE (ZA ISKLYUCHENIEM NEOBYCHNYH SLUCHAEV, TAKIH, KAK SITUACIYA, OPISANNAYA V UPR.~6). tAKIM OBRAZOM, CHISLO PROSMOTROV, KAK PRAVILO, SOSTAVLYAET OKOLO~$\log_2 N$. pRI KAZHDOM PROSMOTRE MY DOLZHNY PEREPISATX VSE $N$~ZAPISEJ, I, KAK POKAZANO V UPR.~2, B\'OLXSHAYA CHASTX VREMENI ZATRACHIVAETSYA V SHAGAH~N3, N4, N5, N8, N9. eSLI SCHITATX, CHTO RAVNYE KLYUCHI VSTRECHAYUTSYA S MALOJ VEROYATNOSTXYU, TO VREMYA, ZATRACHIVAEMOE VO VNUTRENNEM CIKLE, MOZHNO OHARAKTERIZOVATX SLEDUYUSHCHIM OBRAZOM: \ctable{ \hfill# & # & #\cr \hbox{shAG}\hfill&\hfill\hbox{oPERACII}\hfill&\hfill\hbox{vREMYA}\hfill\cr $\matrix{N3\cr}$ & $\matrix{|CMPA|, |JG|, |JE|\cr}$ & $\matrix{3.5u}$ \cr $\hbox{lIBO}\left\{ \matrix{ N4\cr N5\cr }\right.$ & $ \matrix{ |STA|, |INC| \hfill\cr |INC|, |LDA|, |CMPA|, |JGE|\hfill \cr } $ & $\matrix{ \phantom{0.}3u\cr \phantom{0.}6u\cr }$ \cr $\hbox{lIBO}\left\{ \matrix{ N8 \cr N9 \cr }\right.$ & $\matrix{ |STX|, |INC|\hfill \cr |DEC|, |LDX|, |CMPX|, |JGE|\hfill\cr }$ & $\matrix{ \phantom{0.}3u\cr \phantom{0.}6u\cr }$ \cr } tAKIM OBRAZOM, PRI KAZHDOM PROSMOTRE NA KAZHDUYU ZAPISX ZATRACHIVAETSYA $12.5$~EDINIC VREMENI, I OBSHCHEE VREMYA RABOTY ASIMPTOTICHESKI PRIBLIZHAETSYA K~$12.5N\log_2 N$ KAK V SREDNEM, TAK I V NAIHUDSHEM SLUCHAE. eTO MEDLENNEE BYSTROJ SORTIROVKI I NE NASTOLXKO LUCHSHE VREMENI RABOTY PIRAMIDALXNOJ SORTIROVKI, CHTOBY OPRAVDATX VDVOE BOLXSHIJ RASHOD PAMYATI, TAK KAK ASIMPTOTICHESKOE VREMYA RABOTY PROGRAMMY~5.2.3H RAVNO $16N\log_2 N$. %% 198 v ALGORITME~N GRANICY MEZHDU OTREZKAMI POLNOSTXYU OPREDELYAYUTSYA "STUPENXKAMI VNIZ". tAKOJ PODHOD OBLADAET TEM VOZMOZHNYM PREIMUSHCHESTVOM, CHTO ISHODNYE FAJLY S PREOBLADANIEM VOZRASTAYUSHCHEGO \emph{ILI UBYVAYUSHCHEGO} RASPOLOZHENIYA |LEMENTOV MOGUT OBRABATYVATXSYA OCHENX BYSTRO, NO PRI |TOM ZAMEDLYAETSYA OSNOVNOJ CIKL VYCHISLENIJ. vMESTO PROVEROK STUPENEK VNIZ MOZHNO PRINUDITELXNO USTANOVITX DLINU OTREZKOV, SCHITAYA, CHTO VSE OTREZKI ISHODNOGO FAJLA IMEYUT DLINU~$1$, POSLE PERVOGO PROSMOTRA VSE OTREZKI (KROME, VOZMOZHNO, POSLEDNEGO) IMEYUT DLINU 2, \dots, POSLE $k\hbox{-Go}$ PROSMOTRA VSE OTREZKI (KROME, VOZMOZHNO, POSLEDNEGO) IMEYUT DLINU~$2^k$. v OTLICHIE OT "ESTESTVENNOGO" SLIYANIYA V ALGORITME~N TAKOJ SPOSOB NAZYVAETSYA \emph{PROSTYM} DVUHPUTEVYM SLIYANIEM. aLGORITM PROSTOGO DVUHPUTEVOGO SLIYANIYA OCHENX NAPOMINAET ALGORITM~N---ON OPISYVAETSYA, PO SUSHCHESTVU, TOJ ZHE BLOK-SHEMOJ; TEM NE MENEE METODY DOSTATOCHNO OTLICHAYUTSYA DRUG OT DRUGA, I PO|TOMU STOIT ZAPISATX VESX ALGORITM CELIKOM. \alg S.(sORTIROVKA PROSTYM DVUHPUTEVYM SLIYANIEM.) kAK I V ALGORITME~N, PRI SORTIROVKE ZAPISEJ $R_1$, \dots, $R_N$ ISPOLXZUYUTSYA DVE OBLASTI PAMYATI. \st[nACHALXNAYA USTANOVKA.] uSTANOVITX $s\asg0$, $p\asg1$. (sMYSL PEREMENNYH~$s$, $i$, $j$, $k$, $l$, $d$ SM. V ALGORITME~N. zDESX $p$---RAZMER VOZRASTAYUSHCHIH OTREZKOV, KOTORYE BUDUT SLIVATXSYA VO VREMYA TEKUSHCHEGO PROSMOTRA; $q$ I~$r$---KOLICHESTVA NESLITYH |LEMENTOV V OTREZKAH.) \st[pODGOTOVKA K PROSMOTRU.] eSLI $s=0$, TO USTANOVITX $i\asg1$, $j\asg N$, $k\asg N$, $l\asg2N+1$; ESLI $s=1$, TO USTANOVITX $i\asg N+1$, $j\asg2N$, $k\asg0$, $l\asg N+1$. zATEM USTANOVITX $d\asg1$, $q\asg p$, $r\asg p$. \st[sRAVNENIE $K_i:K_j$.] eSLI $K_i>K_j$, TO PEREJTI K SHAGU~\stp{8}. \st[pERESYLKA $R_i$] uSTANOVITX $k\asg k+d$, $R_k\asg R_i$. \st[kONEC OTREZKA?] uSTANOVITX $i\asg i+1$, $q\asg q-1$. eSLI $q > 0$, TO VOZVRATITXSYA K SHAGU~\stp{3}. \st[pERESYLKA $R_j$.] uSTANOVITX $k\asg k+d$. zATEM, ESLI $k=l$, PEREJTI K SHAGU~\stp{13}; V PROTIVNOM SLUCHAE USTANOVITX $R_k\asg R_j$. \st[kONEC OTREZKA?] uSTANOVITX $j\asg j-1$, $r\asg r-1$. eSLI~$r>0$, VOZVRATITXSYA K SHAGU \stp{6}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{12}. \st [pERESYLKA $R_j$.] uSTANOVITX $k\asg k+d$, $R_k\asg R_j$ \st[kONEC OTREZKA?] uSTANOVITX $j\asg j-1$, $r\asg r-1$. eSLI~$r> 0$, TO VOZVRATITXSYA K SHAGU~\stp{3}. \st[pERESYLKA $R_i$.] uSTANOVITX $k\asg k+d$. zATEM, ESLI $k=l$, PEREJTI K SHAGU~\stp{13}; V PROTIVNOM SLUCHAE USTANOVITX $R_k\asg R_i$. %% 199 \st[kONEC OTREZKA?] uSTANOVITX $i\asg i+1$, $q\asg q-1$. eSLI $q > 0$, TO VOZVRATITXSYA K SHAGU \stp{10}. \st[pEREKLYUCHENIE NAPRAVLENIYA.] uSTANOVITX $q\asg p$, $r\asg p$, $d\asg -d$ I VZAIMOZAMENITX $k\xchg l$. vOZVRATITXSYA K SHAGU \stp{3}. \st[pEREKLYUCHENIE OBLASTEJ.] uSTANOVITX $p\asg p+p$. eSLI $p