\input style \chapnotrue \chapno=5 \subchno=2 \subsubchno=2 \subsubchap{Óïòôéòï÷ëá ðïóòåäóô÷ïí ÷ùâïòá} Åýå ïäîï ÷áöîïå óåíåêóô÷ï íåôïäï÷ óïòôéòï÷ëé ïóîï÷áîï îá éäåå íîïçïëòáôîïçï ÷ùâïòá. ×åòïñôîï, ðòïóôåêûáñ óïòôéòï÷ëá ðïóòåäóô÷ïí ÷ùâïòá ó÷ïäéôóñ ë óìåäõàýåíõ: \medskip \item{i)} Îáêôé îáéíåîøûéê ëìàþ; ðåòåóìáôø óïïô÷åôóô÷õàýõà úáðéóø ÷ ïâìáóôø ÷ù÷ïäá é úáíåîéôø ëìàþ úîáþåîéåí "$\infty$" (ëïôïòïå ðï ðòåäðïìïöåîéà âïìøûå ìàâïçï òåáìøîïçï ëìàþá). \item{ii)} Ðï÷ôïòéôø ûáç (i). Îá üôïô òáú âõäåô ÷ùâòáî ëìàþ, îáéíåîøûéê éú ïóôá÷ûéèóñ, ôáë ëáë òáîåå îáéíåîøûéê ëìàþ âùì úáíåîåî îá $\infty$. \item{iii)} Ðï÷ôïòñôø ûáç (i) äï ôåè ðïò, ðïëá îå âõäõô ÷ùâòáîù $N$ úáðéóåê. \medskip \noindent Úáíåôéí, þôï üôïô íåôïä ôòåâõåô îáìéþéñ ÷óåè éóèïäîùè üìåíåîôï÷ äï îáþáìá óïòôéòï÷ëé, á üìåíåîôù ÷ù÷ïäá ïî ðïòïöäáåô ðïóìåäï÷áôåìøîï, ïäéî úá äòõçéí. Ëáòôéîá, ðï óõýåóô÷õ, ðòïôé÷ïðïìïöîá íåôïäõ ÷óôá÷ïë, ÷ ëïôïòïí éóèïäîùå üìåíåîôù äïìöîù ðïóôõðáôø ðïóìåäï÷áôåìøîï, îï ÷ðìïôø äï úá÷åòûåîéñ óïòôéòï÷ëé îéþåçï îå éú÷åóôîï ïâ ïëïîþáôåìøîïí ÷ù÷ïäå. Òñä ÷ùþéóìéôåìøîùè íáûéî (îáðòéíåò, íáûéîù ó ãéëìéþåóëïê âáòáâáîîïê ðáíñôøà) éíååô ÷óôòïåîîõà ëïíáîäõ "îáêôé îáéíåîøûéê üìåíåîô", ëïôïòáñ ÷ùðïìîñåôóñ ó âïìøûïê óëïòïóôøà. Îá ôáëéè íáûéîáè óïòôéòï÷ëá õëáúáîîùí íåôïäïí ïóïâåîîï ðòé÷ìåëáôåìøîá, åóìé ôïìøëï $N$ îå óìéûëïí ÷åìéëï. Ïðéóáîîùê íåôïä ôòåâõåô $N-1$ óòá÷îåîéê ëáöäùê òáú, ëïçäá ÷ùâéòáåôóñ ïþåòåäîáñ úáðéóø; ïî ôáëöå ôòåâõåô ïôäåìøîïê ïâìáóôé ÷ù÷ïäá ÷ ðáíñôé. Éíååôóñ ïþå÷éäîùê óðïóïâ îåóëïìøëï ðïðòá÷éôø óéôõáãéà, éúâåöá÷ ðòé üôïí éóðïìøúï÷áîéñ $\infty$: ÷ùâòáîîïå úîáþåîéå íïöîï úáðéóù÷áôø ÷ óïïô÷åôóô÷õàýõà ðïúéãéà, á úáðéóø, ëïôïòáñ åå úáîéíáìá, ðåòåîïóéôø îá íåóôï ÷ùâòáîîïê. Ôïçäá üôõ ðïúéãéà îå îõöîï òáóóíáôòé÷áôø ÷îï÷ø ðòé ðïóìåäõàýéè ÷ùâïòáè. Îá üôïê éäåå ïóîï÷áî îáû ðåò÷ùê áìçïòéôí óïòôéòï÷ëé ðïóòåäóô÷ïí ÷ùâïòá. \alg S.(Óïòôéòï÷ëá ðïóòåäóô÷ïí ðòïóôïçï ÷ùâïòá.) Úáðéóé $R_1$,~\dots, $R_N$ ðåòåòáúíåýáàôóñ îá ôïí öå íåóôå. Ðïóìå úá÷åòûåîéñ óïòôéòï÷ëé éè ëìàþé âõäõô õðïòñäïþåîù: $K_1\le \ldots\le K_N$. Óïòôéòï÷ëá ïóîï÷áîá îá ïðéóáîîïí ÷ùûå íåôïäå, åóìé îå óþéôáôø ôïçï, þôï âïìåå, õäïâîï, ïëáúù÷áåôóñ, ÷ùâéòáôø óîáþáìá \emph{îáéâïìøûéê} üìåíåîô, úáôåí ÷ôïòïê ðï ÷åìéþéîå é ô. ä. \st[Ãéëì ðï $j$.] ×ùðïìîéôø ûáçé \stp{2} é \stp{3} ðòé $j=N$, $N-1$, \dots, 2. %% 170 \st[Îáêôé~$\max(K_1,~\ldots, K_j)$.] Îáêôé îáéâïìøûéê éú ëìàþåê~$K_j$, $K_{j-1}$,~\dots, $K_1$; ðõóôø üôï âõäåô~$K_i$. \st[Ðïíåîñôø íåóôáíé ó~$R_j$.] ×úáéíïúáíåîéôø úáðéóé~$R_i\xchg R_j$. (Ôåðåòø úáðéóé~$R_j$,~\dots, $R_N$ úáîéíáàô ó÷ïé ïëïîþáôåìøîùå ðïúéãéé.) \algend \picture{Òéó. ~21. Óïòôéòï÷ëá ðòïóôùí ÷ùâïòïí.} × ôáâì.~1 ðïëáúáîï äåêóô÷éå üôïçï áìçïòéôíá îá ûåóôîáäãáôø ëìàþåê, ÷ùâòáîîùè îáíé äìñ ðòéíåòï÷; üìåíåîôù, ðòåôåîäõàýéå îá ôï, þôïâù ïëáúáôøóñ íáëóéíáìøîùíé ÷ï ÷òåíñ ðïéóëá ÷ ûáçå~S2, ÷ùäåìåîù öéòîùí ûòéæôïí. {\catcode`\!=\active\def!#1.{{\bf #1}} \htable{Ôáâìéãá 1}% {Óïòôéòï÷ëá ðïóòåäóô÷ïí ðòïóôïçï ÷ùâïòá}% {\strut\hfil$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr 503 & 087 & 512 & 061 &!908.& 170 &!897.& 275 & 653 & 426 & 154 & 509 & 612 & 677 &!765.&!703.\cr 503 & 087 & 512 & 061 & 703 & 170 &!897.& 275 & 653 & 426 & 154 & 509 & 612 & 677 &!765.& 908 \cr 503 & 087 & 512 & 061 & 703 & 170 &!765.& 275 & 653 & 426 & 154 & 509 & 612 &!677.& 897 & 908 \cr 503 & 087 & 512 & 061 &!703.& 170 &!677.& 275 &!653.& 426 & 154 & 509 &!612.& 765 & 897 & 908 \cr 503 & 087 & 512 & 061 & 612 & 170 &!677.& 275 &!653.& 426 & 154 &!509.& 703 & 765 & 897 & 908 \cr 503 & 087 & 512 & 061 & 612 & 170 & 509 & 275 &!653.&!426.&!154.& 677 & 703 & 765 & 897 & 908 \cr \ldots\cr 061 &!087.& 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr }} Óïïô÷åôóô÷õàýáñ \MIX-ðòïçòáííá äï÷ïìøîï ðòïóôá. \prog S.(Óïòôéòï÷ëá ðïóòåäóô÷ïí ðòïóôïçï ÷ùâïòá.) Ëáë é ÷ ðòåäùäõýéè ðòïçòáííáè üôïê çìá÷ù, úáðéóé, îáèïäñýéåóñ ÷ ñþåêëáè ïô~$|INPUT|+1$ äï~$|INPUT|+N$, óïòôéòõàôóñ îá ôïí öå íåóôå ðï ëìàþõ, úáîéíáàýåíõ ðïìîïå óìï÷ï. Úîáþåîéñ òåçéóôòï÷: $|rA|\equiv \hbox{ôåëõýéê íáëóéíõí}$, $|rI1|\equiv j-1$, $|rI2|\equiv k$ (éîäåëó ðòé ðïéóëå), $|rI3|\equiv i$. Ðòåäðïìáçáåôóñ, þôï~$N\ge 2$. \code START & ENT1 & N-1 & 1 & S1. Ãéëì ðï~$j$. $j\asg N$. 2H & ENT2 & 0,1 & N-1 & S2. Îáêôé~$\max(K_1, \ldots, K_j)$. $k\asg j-1$. & ENT3 & 1,1 & N-1 & $i\asg j$. & LDA & INPUT,3 & N-1 & $|rA|\asg K_i$. 8H & CMPA & INPUT,2 & A & JGE & *+3 & A & Ðåòåèïä, åóìé~$K_i\ge K_k$. & ENT3 & 0,2 & B & × ðòïôé÷îïí óìõþáå õóôáîï÷éôø~$i\asg k$, %% 171 & LDA & INPUT, 3 & B & $|rA|\asg K_i$. & DEC2 & 1 & A & $k\asg k-1$. & J2P & 8B & A & Ðï÷ôïòéôø, åóìé~$k>0$. & LDX & INPUT+1,1& N-1 & S3. Ðïíåîñôø íåóôáíé ó~$R_j$. & STX & INPUT,3 & N-1 & $R_i\asg R_j$. & STA & INPUT+1,1& N-1 & $R_j\asg |rA|$. & DEC1 & 1 & N-1 & J1P & 2B & N-1 & $N\ge j \ge 2$. \endcode \progend ×òåíñ òáâïôù üôïê ðòïçòáííù úá÷éóéô ïô þéóìá üìåíåîôï÷~$N$, þéóìá óòá÷îåîéê~$A$ é þéóìá "ðòá÷ïóôïòïîîéè íáëóéíõíï÷"~$B$. Îåôòõäîï ÷éäåôø, þôï îåúá÷éóéíï ïô úîáþåîéê éóèïäîùè ëìàþåê $$ A=\perm{N}{2}={1\over 2}N(N-1). \eqno(1) $$ Óìåäï÷áôåìøîï, ðåòåíåîîïê ñ÷ìñåôóñ ôïìøëï ÷åìéþéîá~$B$. Îåóíïôòñ îá ÷óà âåúùóëõóîïóôø ðòïóôïçï ÷ùâïòá, îå ôáë ìåçëï ðòïéú÷åóôé ôïþîùê áîáìéú ÷åìéþéîù~$B$. × õðò. ó~3 ðï~6 ðïëáúáîï, þôï $$ B=(\min 0, \ave (N+1)H_n-2N, \max \floor{N^2/4}); \eqno(2) $$ ÷ üôïí óìõþáå ïóïâåîîï éîôåòåóîùí ïëáúù÷áåôóñ íáëóéíáìøîïå úîáþåîéå (óôáîäáòôîïå ïôëìïîåîéå ÷åìéþéîù~$B$ äï óéè ðïò îå ïðòåäåìåîï). Ôáëéí ïâòáúïí, óòåäîåå ÷òåíñ òáâïôù ðòïçòáííù~S òá÷îï $2.5N^2+3(N+1)H_N+3.5N-11$~åäéîéã, ô.~å.\ ïîá ìéûø îåíîïçéí íåäìåîîåå ðòïóôùè ÷óôá÷ïë (ðòïçòáííá~5.2.1S). Éîôåòåóîï óòá÷îéôø áìçïòéôí~S ó óïòôéòï÷ëïê íåôïäïí ðõúùòøëá (áìçïòéôí~5.2.2×), ôáë ëáë íåôïä ðõúùòøëá íïöîï òáóóíáôòé÷áôø ëáë áìçïòéôí ÷ùâïòá, ÷ ëïôïòïí éîïçäá ÷ùâéòáåôóñ âïìåå ïäîïçï üìåíåîôá úá òáú. Ðï üôïê ðòéþéîå ðòé óïòôéòï÷ëå íåôïäïí ðõúùòøëá ðòïéú÷ïäéôóñ íåîøûå óòá÷îåîéê, þåí ðòé ðòïóôïí ÷ùâïòå, é ïîá, ëáë íïöåô ðïëáúáôøóñ, ðòåäðïþôéôåìøîåå. Îï ÷ äåêóô÷éôåìøîïóôé ðòïçòáííá~5.2.2× âïìåå þåí ÷ä÷ïå íåäìåîîåå ðòïçòáííù~S! Óïòôéòï÷ëá íåôïäïí ðõúùòøëá ðòïéçòù÷áåô éú-úá ôïçï, þôï ÷ îåê ÷ùðïìîñåôóñ óìéûëïí íîïçï ïâíåîï÷, ÷ ôï ÷òåíñ ëáë ðòé óïòôéòï÷ëå ðòïóôùí ÷ùâïòïí ðòïéú÷ïäéôóñ ïþåîø íáìï ðåòåóùìïë äáîîùè. \section Õóï÷åòûåîóô÷ï÷áîéñ ðòïóôïçï ÷ùâïòá. Óõýåóô÷õåô ìé ëáëïê-îéâõäø óðïóïâ õìõþûéôø íåôïä ÷ùâïòá, éóðïìøúõåíùê ÷ áìçïòéôíå~S? ×ïúøíåí ë ðòéíåòõ ðïéóë íáëóéíõíá ÷ ûáçå~S2: ÷ïúíïöåî ìé óõýåóô÷åîîï âïìåå âùóôòùê óðïóïâ îáèïöäåîéñ íáëóéíõíá? Ïô÷åô îá üôïô ÷ïðòïó---\emph{îåô!} \proclaim Ìåííá~M. × ìàâïí áìçïòéôíå îáèïöäåîéñ íáëóéíõíá éú $n$~üìåíåîôï÷, ïóîï÷áîîïí îá óòá÷îåîéé ðáò üìåíåîôï÷, îåïâèïäéíï ÷ùðïìîéôø ðï ëòáêîåê íåòå $n-1$~óòá÷îåîéê. %%172 \proof Åóìé ðòïéú÷åäåîï íåîåå $n-1$ óòá÷îåîéê, ôï îáêäõôóñ ðï ëòáêîåê íåòå ä÷á üìåíåîôá, äìñ ëïôïòùè îå âùìï ïâîáòõöåîï îé ïäîïçï üìåíåîôá, ðòå÷ïóèïäñýåçï éè ðï ÷åìéþéîå. Óìåäï÷áôåìøîï, íù ôáë é îå õúîáåí, ëïôïòùê éú üôéè ä÷õè üìåíåîôï÷ âïìøûå, é, úîáþéô, îå óíïöåí ïðòåäåìéôø íáëóéíõí. \proofend Ôáëéí ïâòáúïí, ðòïãåóó ÷ùâïòá, ÷ ëïôïòïí ïôùóëé÷áåôóñ îáéâïìøûéê üìåíåîô, äïìöåî óïóôïñôø îå íåîåå þåí éú $n-1$ ûáçï÷. Ïúîáþáåô ìé üôï, þôï äìñ ÷óåè íåôïäï÷ óïòôéòï÷ëé, ïóîï÷áîîùè îá $n$ ðï÷ôïòîùè ÷ùâïòáè, þéóìï ûáçï÷ îåéúâåöîï âõäåô ðïòñäëá $n^2$? Ë óþáóôøà, ìåííá M ðòéíåîéíá ôïìøëï ë \emph{ðåò÷ïíõ} ûáçõ ÷ùâïòá; ðòé ðïóìåäõàýéè ÷ùâïòáè íïöîï éóðïìøúï÷áôø éú÷ìåþåîîõà òáîåå éîæïòíáãéà. Îáðòéíåò, ÷ õðò.~8 ðïëáúáîï, þôï óòá÷îéôåìøîï ðòïóôïå éúíåîåîéå áìçïòéôíá~S îáðïìï÷éîõ óïëòáýáåô þéóìï óòá÷îåîéê. Òáóóíïôòéí 16 þéóåì, ðòåäóôá÷ìåîîùè ÷ 1-ê óôòïëå ÷ ôáâì.~1. Ïäéî éú óðïóïâï÷ óüëïîïíéôø ÷òåíñ ðòé ðïóìåäõàýéè ÷ùâïòáè---òáúâéôø ÷óå þéóìá îá þåôùòå çòõððù ðï þåôùòå þéóìá. Îáþáôø íïöîï ó ïðòåäåìåîéñ îáéâïìøûåçï, üìåíåîôá ëáöäïê çòõððù, á éíåîîï óïïô÷åôóô÷åîîï ó ëìàþåê $$ 512, 908, 653, 765; $$ ôïçäá îáéâïìøûéê éú üôéè þåôùòåè üìåíåîôï÷ 908 é âõäåô îáéâïìøûéí ÷ï ÷óåí æáêìå. Þôïâù ðïìõþéôø ÷ôïòïê ðï ÷åìéþéîå üìåíåîô, äïóôáôïþîï ðòïóíïôòåôø óîáþáìá ïóôáìøîùå ôòé üìåíåîôá çòõððù, óïäåòöáýåê 908; îáéâïìøûéê éú $\{170, 897, 275\}$ òá÷åî 897, é ôïçäá îáéâïìøûéê óòåäé $$ 512, 897, 653, 765 $$ üôï 897. Áîáìïçéþîï, äìñ ôïçï þôïâù ðïìõþéôø ôòåôéê ðï ÷åìéþéîå üìåíåîô, ïðòåäåìñåí îáéâïìøûéê éú $\{170, 275\}$, á úáôåí îáéâïìøûéê éú $$ 512, 275, 653, 765 $$ é ô. ä. Ëáöäùê ÷ùâïò, ëòïíå ðåò÷ïçï, ôòåâõåô îå âïìåå 6 äïðïìîéôåìøîùè óòá÷îåîéê. ×ïïâýå, åóìé $N$---ôïþîùê ë÷áäòáô, ôï íïöîï òáúäåìéôø æáêì îá $\sqrt N$ çòõðð ðï $\sqrt N$ üìåíåîôï÷ ÷ ëáöäïê; ìàâïê ÷ùâïò, ëòïíå ðåò÷ïçï, ôòåâõåô îå âïìåå þåí $\sqrt{N}-1$ óòá÷îåîéê ÷îõôòé çòõððù òáîåå ÷ùâòáîîïçï üìåíåîôá ðìàó $\sqrt{N}-1$ óòá÷îåîéê óòåäé "ìéäåòï÷ çòõðð". Üôïô íåôïä ðïìõþéì îáú÷áîéå "ë÷áäòáôéþîùê ÷ùâïò"; ïâýåå ÷òåíñ òáâïôù äìñ îåçï åóôø $O(N\sqrt{N})$, þôï óõýåóô÷åîîï ìõþûå, þåí $O(N^2)$. Íåôïä ë÷áäòáôéþîïçï ÷ùâïòá ÷ðåò÷ùå ïðõâìéëï÷áî Ü.~X.~Æòüîäïí [{\sl JACM\/}, {\bf 3} (1956), 152--154]; ïî õëáúáì, þôï üôõ éäåà íïöîï ïâïâýéôø, ðïìõþé÷ ÷ òåúõìøôáôå íåôïä ëõâéþåóëïçï ÷ùâïòá, ÷ùâïòá þåô÷åòôïê óôåðåîé é ô. ä. Îáðòéíåò, íåôïä ëõâéþåóëïçï %%173 ÷ùâïòá óïóôïéô ÷ ôïí, þôïâù òáúäåìéôø æáêì îá $\root 3\of N$ âïìøûéè çòõðð, ëáöäáñ éú ëïôïòùè óïäåòöéô ðï $\root 3\of N$ íáìùè çòõðð ðï $\root 3\of N$ úáðéóåê; ÷òåíñ òáâïôù ðòïðïòãéïîáìøîï $N\root 3\of N$. Åóìé òáú÷éôø üôõ éäåà äï åå ðïìîïçï úá÷åòûåîéñ, ôï íù ðòéäåí ë ôïíõ, þôï Æòüîä îáú÷áì "÷ùâïò $n$-ê óôåðåîé", ïóîï÷áîîùê îá óôòõëôõòå âéîáòîïçï äåòå÷á. ×òåíñ òáâïôù üôïçï íåôïäá ðòïðïòãéïîáìøîï $N \log N$; íù âõäåí îáúù÷áôø åçï \dfn{÷ùâïòïí éú äåòå÷á}. \section ×ùâïò éú äåòå÷á. Ðòéîãéðù óïòôéòï÷ëé ðïóòåäóô÷ïí ÷ùâïòá éú äåòå÷á âõäåô ìåçþå ÷ïóðòéîñôø, åóìé ÷ïóðïìøúï÷áôøóñ áîáìïçéåê ó ôéðéþîùí "ôõòîéòïí ó ÷ùâù÷áîéåí". Òáóóíïôòéí, îáðòéíåò, òåúõìøôáôù óïòå÷îï÷áîéñ ðï îáóôïìøîïíõ ôåîîéóõ, ðïëáúáîîùå îá òéó.~22. Äöéí ðïâåöäáåô Äïîá, á Äöï ðïâåöäáåô Äöåëá; úáôåí ÷ óìåäõàýåí ôõòå Äöï ÷ùéçòù÷áåô õ Äöéíá é ô. ä. Îá òéó.~22 ðïëáúáîï, þôï Äöï---þåíðéïî óòåäé ÷ïóøíé óðïòôóíåîï÷, á äìñ ôïçï, þôïâù ïðòåäåìéôø üôï, ðïôòåâï÷áìïóø $8-1=7$ íáôþåê (ô. å. óòá÷îåîéê). Äéë ÷ï÷óå îå ïâñúáôåìøîï âõäåô ÷ôïòùí ðï óéìå éçòïëïí: ìàâïê éú óðïòôóíåîï÷, õ ëïôïòùè ÷ùéçòáì Äöï, ÷ëìàþáñ äáöå ðòïéçòá÷ûåçï ÷ ðåò÷ïí ôõòå Äöåëá, íïç âù ïëáúáôøóñ ÷ôïòùí ðï óéìå éçòïëïí. ×ôïòïçï éçòïëá íïöîï ïðòåäåìéôø, úáóôá÷é÷ Äöåëá óùçòáôø ó Äöéíïí, á ðïâåäéôåìñ üôïçï íáôþá---ó Äéëïí; ÷óåçï ä÷á äïðïìîéôåìøîùè íáôþá ôòåâõåôóñ äìñ ïðòåäåìåîéñ ÷ôïòïçï ðï óéìå éçòïëá, éóèïäñ éú ôïçï óïïôîïûåîéñ óéì, ëïôïòïå íù úáðïíîéìé éú ðòåäùäõýéè éçò. ×ïïâýå íïöîï "÷ù÷åóôé" éçòïëá, îáèïäñýåçïóñ ÷ ëïòîå äåòå÷á, é úáíåîéôø åçï þòåú÷ùþáêîï óìáâùí éçòïëïí. Ðïäóôáîï÷ëá üôïçï óìáâïçï éçòïëá ïúîáþáåô, þôï ðåò÷ïîáþáìøîï ÷ôïòïê ðï óéìå óðïòôóíåî óôáîåô ôåðåòø îáéìõþûéí, é éíåîîï ïî ïëáöåôóñ ÷ ëïòîå, åóìé ÷îï÷ø ÷ùþéóìéôø ðïâåäéôåìåê ÷ ÷åòèîéè õòï÷îñè äåòå÷á. Äìñ üôïçï îõöîï éúíåîéôø ìéûø ïäéî ðõôø, ÷ äåòå÷å, ôáë þôï äìñ ÷ùâïòá óìåäõàýåçï ðï óéìå éçòïëá îåïâèïäéíï íåîåå $\lceil \log_2 N\rceil$) äïðïìîéôåìøîùè óòá÷îåîéê. Óõííáòîïå %%174 \picture{Òéó. 23. Ðòéíåò óïòôéòï÷ëé ðïóòåäóô÷ïí ÷ùâïòá éú äåòå÷á...} %% 175 ÷òåíñ ÷ùðïìîåîéñ ôáëïê óïòôéòï÷ëé ðïóòåäóô÷ïí ÷ùâïòá ðòéíåòîï ðòïðïòãéïîáìøîï $N\log N$. Îá òéó.~23 óïòôéòï÷ëå ðïóòåäóô÷ïí ÷ùâïòá éú äåòå÷á ðïä÷åòçáàôóñ îáûé 16 þéóåì. Úáíåôéí, þôï äìñ ôïçï, þôïâù úîáôø, ëõäá ÷óôá÷ìñôø óìåäõàýéê üìåíåîô "$-\infty$", îåïâèïäéíï ðïíîéôø, ïôëõäá ðòéûåì ëìàþ, îáèïäñýéêóñ ÷ ëïòîå. Ðïüôïíõ õúìù òáú÷åô÷ìåîéñ ÷ äåêóô÷éôåìøîïóôé óïäåòöáô õëáúáôåìé éìé éîäåëóù, ïðéóù÷áàýéå ðïúéãéà ëìàþá, á îå óáí ëìàþ. Ïôóàäá óìåäõåô, þôï îåïâèïäéíá ðáíñôø äìñ $N$ éóèïäîùè úáðéóåê, $N-1$ óìï÷-õëáúáôåìåê é $N$ ÷ù÷ïäéíùè úáðéóåê. (Òáúõíååôóñ, åóìé ÷ù÷ïä \picture{Òéó. 24. Ðòéíåîåîéå ëïòðïòáôé÷îïê óéóôåíù ÷ùä÷éöåîéê ë óïòôéòï÷ëå. Ëáöäùê ðïäîéíáåôóñ îá ó÷ïê õòï÷åîø îåëïíðåôåîôîïóôé ÷ éåòáòèéé.} éäåô îá ìåîôõ éìé îá äéóë, ôï îå îõöîï óïèòáîñôø ÷ù÷ïäéíùå úáðéóé ÷ ïðåòáôé÷îïê ðáíñôé.) Þôïâù ïãåîéôø ôå úáíåþáôåìøîùå õóï÷åòûåîóô÷ï÷áîéñ, ëïôïòùå íù óïâéòáåíóñ ïâóõäéôø, ÷ üôïí íåóôå óìåäõåô ðòåò÷áôø þôåîéå äï ôåè ðïò, ðïëá ÷ù îå ïó÷ïéôåóø ó ÷ùâïòïí éú äåòå÷á èïôñ âù îáóôïìøëï, þôï òåûåîéå õðò.~10 îå óïóôá÷éô äìñ ÷áó îéëáëïçï ôòõäá. Ïäîá éú íïäéæéëáãéê ÷ùâïòá éú äåòå÷á, ÷÷åäåîîáñ, ðï óõýåóô÷õ, Ë.~Ü.~Áê÷åòóïîïí [A Programming Language (Wiley, 1962), 223--227], õóôòáîñåô îåïâèïäéíïóôø õëáúáôåìåê, óìåäõàýéí ïâòáúïí ïóõýåóô÷ìññ "úáçìñäù÷áîéå ÷ðåòåä": ëïçäá ðïâåäéôåìø íáôþá îá îéöîåí õòï÷îå ðïäîéíáåôóñ ÷÷åòè, ôï îá îéöîåí õòï÷îå åçï óòáúõ öå íïöîï úáíåîéôø îá "$-\infty$"; ëïçäá öå ðïâåäéôåìø ðåòåíåýáåôóñ ÷÷åòè ó ïäîïçï òáú÷åô÷ìåîéñ îá äòõçïå, ôï åçï íïöîï úáíåîéôø éçòïëïí, ëïôïòùê ÷ ëïîãå ëïîãï÷ ÷óå òá÷îï äïìöåî ðïäîñôøóñ, îá åçï ðòåöîåå íåóôï (á éíåîîï îáéâïìøûéí éú ä÷õè ëìàþåê, òáóðïìïöåîîùè ðïä îéí). ×ùðïìîé÷ üôõ ïðåòáãéà óôïìøëï òáú, óëïìøëï ÷ïúíïöîï, ðòéäåí ïô òéó.~23(á) ë òéó.~24. Ëïìø óëïòï äåòå÷ï ðïóôòïåîï ôáëéí ïâòáúïí, íïöîï ðòïäïìöáôø óïòôéòï÷ëõ îå "÷ïóèïäñýéí" íåôïäïí, ðïëáúáîîùí îá òéó.~23, á "îéóèïäñýéí": ÷ù÷ïäéôóñ üìåíåîô, îáèïäñýéêóñ %% 176 ÷ ëïòîå, ðåòåíåýáåôóñ ÷÷åòè îáéâïìøûéê éú åçï ðïôïíëï÷, ðåòåíåýáåôóñ ÷÷åòè îáéâïìøûéê éú ðïôïíëï÷ ðïóìåäîåçï é ô. ä. Ðòïãåóó îáþéîáåô ðïèïäéôø îå óôïìøëï îá ôõòîéò ðï îáóôïìøîïíõ ôåîîéóõ, óëïìøëï îá ëïòðïòáôé÷îõà óéóôåíõ ÷ùä÷éöåîéê. Þéôáôåìø äïìöåî õñóîéôø, þôï õ îéóèïäñýåçï íåôïäá åóôø ÷áöîïå äïóôïéîóô÷ï---ïî ðïú÷ïìñåô éúâåöáôø ìéûîéè óòá÷îåîéê $-\infty$ ó~$-\infty$. (Ðïìøúõñóø ÷ïóèïäñýéí íåôïäïí, íù îá âïìåå ðïúäîéè óôáäéñè óïòôéòï÷ëé ÷óàäõ îáôùëáåíóñ îá $-\infty$, á ðòé îéóèïäñýåí íåôïäå íïöîï îá ëáöäïê óôáäéé úáëáîþé÷áôø ðòåïâòáúï÷áîéå äåòå÷á óòáúõ öå ðïóìå úáîåóåîéñ $-\infty$.) \picture{Òéó. 25. Ðïóìåäï÷áôåìøîïå òáóðòåäåìåîéå ðáíñôé äìñ ðïìîïçï âéîáòîïçï äåòå÷á.} Îá òéó.~23 é~24 éúïâòáöåîù \emph{ðïìîùå âéîáòîùå äåòå÷øñ} ó 16 ëïîãå÷ùíé õúìáíé (óò. ó ð.~2.3.4.5); ôáëéå äåòå÷øñ õäïâîï èòáîéôø ÷ ðïóìåäï÷áôåìøîùè ñþåêëáè ðáíñôé, ëáë ðïëáúáîï îá òéó.~25. Úáíåôéí, þôï ïôãïí õúìá îïíåò $k$ ñ÷ìñåôóñ õúåì $\lfloor k/2\rfloor$ , á åçï ðïôïíëáíé ñ÷ìñàôóñ õúìù $2k$ é $2k+1$. Ïôóàäá ÷ùôåëáåô åýå ïäîï ðòåéíõýåóô÷ï îéóèïäñýåçï íåôïäá, ðïóëïìøëõ úáþáóôõà úîáþéôåìøîï ðòïýå ðòïä÷éçáôøóñ ÷îéú ïô õúìá $k$ ë õúìáí $2k$ é~$2k+1$, þåí ÷÷åòè ïô õúìá $k$ ë õúìáí $k\oplus 1$ é~$\lfloor k/2\rfloor$. (Úäåóø þåòåú $k\oplus 1$ ïâïúîáþåîï þéóìï $k+1$ éìé $k-1$ ÷ úá÷éóéíïóôé ïô ôïçï, ñ÷ìñåôóñ ìé $k$ þåôîùí éìé îåþåôîùí.) Äï óéè ðïò ÷ îáûéè ðòéíåòáè ÷ùâïòá éú äåòå÷á ÷ ôïê éìé éîïê íåòå ðòåäðïìáçáìïóø, þôï $N$ åóôø óôåðåîø 2; ÷ äåêóô÷éôåìøîïóôé íïöîï òáâïôáôø ó ðòïéú÷ïìøîùí úîáþåîéåí $N$, ôáë ëáë ðïìîïå âéîáòîïå äåòå÷ï ó $N$ ëïîãå÷ùíé õúìáíé îåôòõäîï ðïóôòïéôø äìñ ìàâïçï N. Íù ðïäïûìé ôåðåòø ë ïóîï÷îïíõ ÷ïðòïóõ: îåìøúñ ìé ÷ îéóèïäñýåí íåôïäå ïâïêôéóø óï÷óåí âåú "$-\infty$"? Îå ðòá÷äá ìé, âùìï âù þõäåóîï, åóìé âù ÷óà óõýåóô÷åîîõà éîæïòíáãéà, éíåàýõàóñ îá òéó.~24, õäáìïóø òáóðïìïöéôø ÷ ñþåêëáè 1--16 %%177 ðïìîïçï âéîáòîïçï äåòå÷á âåú ÷óñëéè âåóðïìåúîùè "äùò", óïäåòöáýéè $-\infty$? Ðïòáúíùóìé÷, íïöîï ðòéêôé ë ÷ù÷ïäõ, þôï üôá ãåìø ÷ äåêóô÷éôåìøîïóôé äïóôéöéíá, ðòéþåí îå ôïìøëï éóëìàþáåôóñ $-\infty$, îï é ðïñ÷ìñåôóñ ÷ïúíïöîïóôø óïòôéòï÷áôø $N$ úáðéóåê îá ôïí öå íåóôå âåú ÷óðïíïçáôåìøîïê ïâìáóôé ÷ù÷ïäá. Üôï ðòé÷ïäéô ë åýå ïäîïíõ ÷áöîïíõ áìçïòéôíõ óïòôéòï÷ëé. Åçï á÷ôïò Äö.~Õ.~Äö.~Õéìøñíó [{\sl CACM\/}, {\bf 7} (1964), 347--348] ïëòåóôéì ó÷ïê áìçïòéôí "ðéòáíéäáìøîïê óïòôéòï÷ëïê" ("heapsort"). \section Ðéòáíéäáìøîáñ óïòôéòï÷ëá. Âõäåí îáúù÷áôø æáêì ëìàþåê $K_1$, $K_2$, \dots, $K_N$ "ðéòáíéäïê", åóìé $$ K_{\lfloor j/2\rfloor}\ge K_j \rem{ ðòé $1\le \lfloor j/2\rfloor1$, ôï õóôáîï÷éôø $l\asg l-1$, $R\asg R_l$, $K\asg K_l$. (Åóìé $l>1$, üôï ïúîáþáåô, þôï ðòïéóèïäéô %% 178 ðòïãåóó ðòåïâòáúï÷áîéñ éóèïäîïçï æáêìá ÷ ðéòáíéäõ; åóìé öå $l= 1$, ôï üôï úîáþéô, þôï ëìàþé $K_1$, $K_2$, \dots, $K_r$ õöå ïâòáúõàô ðéòáíéäõ.) × ðòïôé÷îïí óìõþáå õóôáîï÷éôø $R\asg R_r$, $K\asg K_r$, $R_r\asg R_1$ é $r\asg r-1$; åóìé ÷ òåúõìøôáôå ïëáúáìïóø, þôï $r=1$, ôï õóôáîï÷éôø $R_1\asg R$ é úá÷åòûéôø òáâïôõ áìçïòéôíá. \st[Ðòéçïôï÷éôøóñ ë "ðòïôáóëé÷áîéà".] Õóôáîï÷éôø $j\asg l$. (Ë üôïíõ íïíåîôõ $$ K_\floor{j/2}\ge K_j \rem{ðòé $l<\floor{j/2}r$, ôï ðåòåêôé ë ûáçõ \stp{8}. \st[Îáêôé "âïìøûåçï" óùîá.] Åóìé $K_j