\input style %%150 дкъ янпрхпнбйх) ашярпюъ янпрхпнбйю опебпюыюеряъ б нрмчдэ ме ашярпсч. Бпелъ ее пюанрш ярюмнбхряъ опнонпжхнмюкэмшл $N^2$, ю ме $N\log N$ (ял. соп.~25). Б нркхвхе нр дпсцху юкцнпхрлнб янпрхпнбйх, йнрнпше мюл бярпевюкхяэ, юкцнпхрл Q опедонвхрюер месонпъднвеммше тюикш! Б сонлъмсрни ярюрэе Унюпю опедкнфемш дбю яонянаю онопюбхрэ яхрсюжхч, нямнбшбючыхуяъ мю бшанпе ксвьецн гмювемхъ опнбепъелнцн йкчвю $K$, йнрнпши сопюбкъер пюгдекемхел. Ндмю хг ецн пейнлемдюжхи янярнхр .б рнл, врнаш б онякедмеи вюярх ьюцю Q2 бшахпюрэ \emph{яксвюимне} жекне вхякн $q$ лефдс $l$ х~$r$; б щрнл ьюце лнфмн гюлемхрэ хмярпсйжхх "$K\asg K_l$, $R\asg R_l$" мю $$ K\asg K_q, \quad R\asg R_q, \quad R_q\asg R_l. \eqno(27) $$ Янцкюямн тнплскюл (25), рюйхе яксвюимше жекше вхякю опхдеряъ бшвхякърэ б япедмел кхьэ $2(N+1)/(M+2)-1$~пюг, рюй врн днонкмхрекэмне бпелъ пюанрш меясыеярбеммн, ю яксвюимши бшанп---унпньюъ гюыхрю нр ноюямнярх нйюгюрэяъ б мюхусдьеи яхрсюжхх. Брнпне опедкнфемхе Унюпю янярнхр б рнл, врнаш опнялнрперэ меанкэьни свюярнй тюикю х мюирх ледхюмс дкъ щрни янбнйсомнярх дюммшу. Рюйнлс ондундс онякеднбюк П. Й. Яхмцкрнм [{\sl CACM\/}, {\bf 12} (1969), 185--187], йнрнпши опедкнфхк б йювеярбе $K_q$ апюрэ ледхюмс рпеу гмювемхи $$ K_l, \quad K_{\lfloor(l+r)/2\rfloor}, \quad K_r. \eqno(28) $$ Опнжедспю Яхмцкрнмю янйпюыюер вхякн япюбмемхи я $2N \ln N$ опхлепмн дн ${12\over7}N\ln N$ (ял. соп. 29). Лнфмн онйюгюрэ, врн. б щрнл яксвюе $B_N$ юяхлорнрхвеяйх опхакхфюеряъ й $C_N/5$, ю ме й~$C_N/6$, рюй врн лернд ледхюмш меяйнкэйн сбекхвхбюер бпелъ, гюрпювхбюелне мю оепеяшкйс дюммшу, онщрнлс наыее бпелъ пюанрш янйпюыюеряъ опхлепмн, мю 8\%. (Ондпнамши юмюкхг ял. б соп.56.) Бпелъ пюанрш б мюхусдьел яксвюе бяе еые онпъдйю $N^2$, ндмюйн я рюйхл ледкеммшл онбедемхел юкцнпхрлю бпъд кх йнцдю-кхан опхдеряъ бярперхрэяъ мю опюйрхйе. С.~Д.~Тпщигеп х Ю.~В.~Люй-Йеккюп [{\sl JACM\/}, {\bf 17} (1970), 496--507] опедкнфхкх пюяялюрпхбюрэ янбнйсомнярэ цнпюгдн анкэьецн на╝елю хг $2^k-1$ гюохяеи, цде $k$ бшахпюеряъ рюй, врнаш $2^k\approx N/\ln N$. Щрс янбнйсомнярэ лнфмн нрянпрхпнбюрэ нашвмшл лернднл ашярпни янпрхпнбйх, оняке вецн щкелемрш бярюбкъчряъ япедх нярюкэмшу гюохяеи гю $k$ опнялнрпнб бяецн тюикю (б пегскэрюре тюик асдер пюгдекем мю $2^k$ ондтюикнб, нцпюмхвеммшу щкелемрюлх оепбнмювюкэмни янбнйсомнярх). Мю гюйкчвхрекэмнл щрюое янпрхпсчряъ онксвеммше ондтюикш. Япедмее вхякн, япюбмемхи, бшонкмъелшу рюйни опнжедспни "янпрхпнбйх янбнйсомнярх", опхлепмн рюйне фе, йюй х дкъ лерндю ледхюмш Яхмцкрнмю, йнцдю $N$ %%151 мюундхряъ б опюйрхвеяйнл дхюоюгнме гмювемхи, мн опх $N\to\infty$ нмн юяхлорнрхвеяйх опхакхфюеряъ й $N\log_2N$. \section Налеммюъ онпюгпъдмюъ янпрхпнбйю. Лш ондундхл реоепэ й лерндс, янбепьеммн нркхвмнлс нр бяеу яуел янпрхпнбйх, йнрнпше пюяялюрпхбюкхяэ опефде; б мел хяонкэгсеряъ \emph{дбнхвмне опедярюбкемхе} йкчвеи, х.онрнлс нм опедмюгмювем хяйкчвхрекэмн дкъ дбнхвмшу люьхм. Блеярн рнцн врнаш япюбмхбюрэ лефдс янани дбю йкчвю, б щрнл лернде опнбепъеряъ, пюбмш кх 0 хкх 1 нрдекэмше ахрш йкчвю. Б дпсцху нрмньемхъу нм накюдюер уюпюйрепхярхйюлх налеммни янпрхпнбйх х мю яюлнл деке нвемэ мюонлхмюер ашярпсч янпрхпнбйс. Рюй йюй нм гюбхяхр нр пюгпъднб йкчвю, опедярюбкеммнцн б дбнхвмни яхяреле явхякемхъ, лш мюгшбюел ецн "налеммни онпюгпъдмни янпрхпнбйни". Б наыху вепрюу щрнр юкцнпхрл лнфмн нохяюрэ якедсчыхл напюгнл: \enumerate \li Онякеднбюрекэмнярэ янпрхпсеряъ \emph{он ярюпьелс гмювюыелс дбнхвмнлс ахрс} рюй, врнаш бяе йкчвх, мювхмючыхеяъ я 0, нйюгюкхяэ оепед бяелх йкчвюлх, мювхмючыхлхяъ я 1. Дкъ щрнцн мюдн мюирх яюлши кебши йкчв $K_i$, мювхмючыхияъ я 1, х яюлши опюбши йкчв $K_j$, мювхмючыхияъ я 0, оняке вецн $R_i$ х $R_j$ лемъчряъ леярюлх, х опнжеяя онбрнпъеряъ, онйю ме ярюмер $i>j$. \li Осярэ $F_0$---лмнфеярбн щкелемрнб, мювхмючыхуяъ я 0, ю $F_1$---бяе нярюкэмше. Опхлемхл й $F_0$ онпюгпъдмсч янпрхпнбйс (мювюб реоепэ ян \emph{брнпнцн} ахрю якебю, ю ме ян ярюпьецн) дн реу онп, онйю лмнфеярбн $F_0$ .ме асдер онкмнярэч нрянпрхпнбюмн; гюрел опндекюел рн фе я $F_1$. \enumend Мюопхлеп, б рюак.~3 онйюгюмн, йюй деиярбсер налеммюъ онпюгпъдмюъ янпрхпнбйю мю мюьх 16 яксвюимшу вхяек, гюохяюммшу реоепэ б бняэлепхвмни яхяреле явхякемхъ. Мю ярюдхх 1 онйюгюм хяундмши тюик; оняке налемнб он оепбнлс ахрс опхундхл йн брнпни ярюдхх. Мю брнпни ярюдхх янпрхпсеряъ оепбюъ цпсоою он брнпнлс, ахрс, мю рперэеи---он рперэелс ахрс. (Вхрюрекэ днкфем лшякеммн опенапюгнбюрэ бняэлепхвмше вхякю б 10-пюгпъдмше дбнхвмше.) Йнцдю лш оняке янпрхпнбйх он .вербепрнлс ахрс днярхцюел оърни ярюдхх, рн намюпсфхбюел, врн йюфдюъ хг нярюбьхуяъ цпсоо яндепфхр бяецн он ндмнлс щкелемрс,- рюй врн щрс вюярэ тюикю лнфмн анкэье ме пюяялюрпхбюрэ. Гюохяэ "${}^4[0232\ 0252]$" нгмювюер, врн ондтюик $0232\ 0252$ еые опедярнхр янпрхпнбюрэ он вербепрнлс ахрс якебю. Б щрнл йнмйпермнл яксвюе янпрхпнбйю он вербепрнлс ахрс ме дюер мхвецн мнбнцн; врнаш пюгдекхрэ щкелемрш, менаундхлн днапюрэяъ дн оърнцн ахрю. Беяэ опнжеяя янпрхпнбйх, онйюгюммши б рюак.~3, бшонкмъеряъ гю 22 ярюдхх; щрн меяйнкэйн анкэье яннрберярбсчыецн вхякю б ашярпни янпрхпнбйе (рюак.~2). Вхякн опнбепнй ахрнб 82 рюйфе бекхйн; мн лш сбхдхл, врн вхякн опнбепнй ахрнб опх анкэьху 151 %%152 \picture{Рюакхжю 3} %%153 $N$ б деиярбхрекэмнярх лемэье, вел вхякн япюбмемхи б ашярпни янпрхпнбйе, б опедонкнфемхх н пюбмнлепмнл пюяопедекемхх йкчвеи. Наыее вхякн налемнб б рюак.~3 пюбмн 17, р. е. беяэлю слепеммн. Гюлерхл, врн, унръ янпрхпсчряъ 10-ахрнбше вхякю, б дюммнл опхлепе опх опнбепйе ахрнб мхйнцдю ме опхундхряъ хдрх дюкэье яедэлнцн ахрю. Йюй х опх ашярпни янпрхпнбйе, дкъ упюмемхъ "хмтнплюжхх н цпюмхжюу" ондтюикнб, нфхдючыху янпрхпнбйх, лнфмн бняонкэгнбюрэяъ ярейнл. Блеярн рнцн врнаш янпрхпнбюрэ б оепбсч нвепедэ мюхлемэьхи хг ондтюикнб, сднамн опнярн опндбхцюрэяъ якебю мюопюбн, рюй йюй пюглеп ярейю б. щрнл яксвюе мхйнцдю ме опебгнидер вхякю ахрнб б янпрхпселшу йкчвюу. Б юкцнпхрле, опхбедеммнл мхфе, щкелемр ярейю $(r, b)$ сйюгшбюер мю рн, врн ондтюик я опюбни цпюмхжеи $r$ нфхдюер янпрхпнбйх он ахрс $b$; кебсч цпюмхжс лнфмн ме гюонлхмюрэ б ярейе: нмю бяецдю гюдюмю меъбмн, оняйнкэйс б щрни опнжедспе тюик бяецдю напюаюршбюеряъ якебю мюопюбн. \alg R.(Налеммюъ онпюгпъдмюъ янпрхпнбйю.) Гюохях $R_1$, \dots, $R_N$ оепепюглеыючряъ мю рнл фе леяре; оняке гюбепьемхъ янпрхпнбйх ху йкчвх асдср сонпъднвемш: $K_1\le \ldots \le K_N$. Опедонкюцюеряъ, врн бяе йкчвх---$m$-пюгпъдмше дбнхвмше вхякю $(a_1\ a_2\ \ldots\ a_m)_2$; $i$-и он ярюпьхмярбс ахр $a_i$ мюгшбюеряъ "ахр $i$" йкчвю. Рпеасеряъ бяонлнцюрекэмши ярей, блеыючыхи дн $m-1$ щкелемрнб. Щрнр юкцнпхрл, он ясыеярбс, якедсер опнжедспе налеммни онпюгпъдмни янпрхпнбйх я пюгдекемхълх, нохяюммни бшье; бнглнфмш мейнрнпше сянбепьемярбнбюмхъ я жекэч онбшьемхъ щттейрхбмнярх (нмх нохяюмш дюкее б рейяре х б сопюфмемхъу). \st[Мювюкэмюъ сярюмнбйю.] Носярньхрэ ярей х сярюмнбхрэ $l\asg 1$, $r\asg N$, $b\asg 1$. \st[Мювюрэ мнбсч ярюдхч.] (Лш унрекх аш реоепэ нрянпрхпнбюрэ ондтюик $R_l\le \ldots \le R_r$ он ахрс $b$; он ялшякс юкцнпхрлю $l\le r$.) Еякх $l=r$, рн оепеирх й ьюцс \stp{10} (рюй йюй тюик, янярнъыхи хг ндмнцн якнбю, сфе нрянпрхпнбюм). Б опнрхбмнл яксвюе сярюмнбхрэ $i\asg l$, $j\asg r$. \st[Опнбепхрэ $K_i$ мю 1.] Опнбепхрэ ахр $b$ йкчвю $K_i$.. Еякх нм пюбем 1, рн оепеирх й ьюцс \stp{6}. \st[Сбекхвхрэ $i$.] Сбекхвхрэ $i$ мю 1. Еякх $i\le j$, рн бнгбпюрхрэяъ й ьюцс \stp{3}; б опнрхбмнл яксвюе оепеирх й ьюцс \stp{8}. \st[Опнбепхрэ $K_{j+1}$ мю 0.] Опнбепхрэ ахр $b$ йкчвю $K_{j+1}$. Еякх нм пюбем 0, рн оепеирх й ьюцс \stp{7}. \st[Слемэьхрэ $j$.] Слемэьхрэ $j$ мю 1. Еякх$ i\le j$, рн оепеирх й ьюцс \stp{5}; б опнрхбмнл яксвюе оепеирх й ьюцс \stp{8}. \st[Онлемърэ леярюлх $R_i$, $R_{j+1}$]. Онлемърэ леярюлх $R_i\xchg R_{j+1}$, гюрел оепеирх й ьюцс \stp{4}. \st[Опнбепхрэ нянаше яксвюх.] (Й щрнлс лнлемрс ярюдхъ пюгдекемхъ %%154 гюбепьемю, $i=j+1$, ахр $b$ йкчвеи~$K_l$, \dots, $K_j$ пюбем~$0$, ю ахр~$b$ йкчвеи $K_i$, \dots, $K_r$ пюбем~$1$.) Сбекхвхрэ $b$ мю~1. Еякх $b>m$, цде $m$---наыее вхякн ахрнб б йкчвюу, рн оепеирх й ьюцс~\stp{10}. (Щрн нгмювюер, врн ондтюик $R_l$ \dots $R_r$ нрянпрхпнбюм. Еякх б тюике ме лнфер ашрэ пюбмшу йкчвеи, рн рюйсч опнбепйс лнфмн ме декюрэ.) Б опнрхбмнл яксвюе, еякх~$jm$;}\cr K&=\hbox{вхякн яксвюеб, йнцдю б ьюце R8 $b\le m$, $j=l$;}\cr L&=\hbox{вхякн яксвюеб, йнцдю б ьюце R8 $b\le m$, $jm$. Ндхм опхелкелши яоняна хяопюбхрэ щрнр меднярюрнй опедкнфем б нрбере й соп.~40. Йюй налеммюъ онпюгпъдмюъ янпрхпнбйю, рюй х ашярпюъ янпрхпнбйю нямнбюмш мю хдее пюгдекемхъ. Гюохях лемъчряъ леярюлх дн реу онп, онйю тюик ме асдер пюгахр мю дбе вюярх: кебши ондтюик, б йнрнпнл бяе йкчвх $\le K$ опх мейнрнпнл $K$, х опюбши ондтюик, б йнрнпнл бяе йкчвх $\ge K$. Б ашярпни янпрхпнбйе б йювеярбе $K$ бшахпюеряъ пеюкэмши йкчв хг тюикю, б рн бпелъ йюй б налеммни онпюгпъдмни янпрхпнбйе, он ясыеярбс, бшахпюеряъ мейнрнпши хяйсяярбеммши йкчв мю нямнбе дбнхвмшу опедярюбкемхи. Врн йюяюеряъ хярнпхвеяйни ярнпнмш декю, рн налеммсч онпюгпъдмсч янпрхпнбйс нрйпшкх О.~Ухкэдеапюмдр, Ц.~Хяахрж, X.~Пюигхмц х Ф.~Ьбюпж [{\sl JACM\/}, {\bf 6} (1959), 156--163] опхлепмн гю цнд дн хгнаперемхъ ашярпни янпрхпнбйх. Бнглнфмш рюйфе х дпсцхе яуелш пюгдекемхъ; мюопхлеп, Дфнм Люййюпрх опедкнфхк бшахпюрэ $K\approx{1\over2}(u+v)$, еякх хгбеярмн, врн бяе йкчвх кефюр б дхюоюгнме лефдс $u$ х~$v$. Еые ндмс ярпюрецхч пюгдекемхъ опедкнфхк Л.~У.~бюм~Щлдем [{\sl CACM\/}, {\bf 13} (1970), 563--567]: блеярн рнцн врнаш бшахпюрэ $K$ гюпюмее, лш "сгмюел", йюйнбн лнфер ашрэ унпньее гмювемхе $K$, якедъ б опнжеяяе пюгдекемхъ гю хглемемхел бекхвхм $K'=\max(K_l, \ldots, K_i)$ х~$K''=\min(K_j, \ldots, K_r)$. Лнфмн сбекхвхбюрэ $i$ дн реу онп, онйю ме бярперхряъ йкчв, анкэьхи $K'$; гюрел мювюрэ слемэьюрэ $j$, онйю ме бярперхряъ йкчв, лемэьхи $K''$, оняке вецн онлемърэ ху леярюлх х/хкх срнвмхрэ гмювемхъ~$K'$ х~$K''$. Щлохпхвеяйхе реярш дкъ щрни хмрепбюкэмни янпрхпнбйх онйюгшбючр, врн нмю рпеасер нйнкн $1.64N\ln N=1.14N\log_2N$ япюбмемхи. Щрн едхмярбеммши лернд, наясфдюелши б щрни ймхце, дкъ онбедемхъ йнрнпнцн еые ме мюидемн юдейбюрмнцн ренперхвеяйнцн на╝ъямемхъ. Нанаыемхе налеммни онпюгпъдмни янпрхпнбйх мю яксвюи яхярелш явхякемхъ я нямнбюмхел, анкэьхл 2, наясфдюеряъ б о.~5.2.5. %%158 \section * Юяхлорнрхвеяйхе лерндш. Юмюкхг юкцнпхрлнб налеммни янпрхпнбйх опхбндхр й мейнрнпшл нянаеммн онсвхрекэмшл люрелюрхвеяйхл гюдювюл, йнрнпше онгбнкъчр анкэье сгмюрэ н яонянаюу нопедекемхъ юяхлорнрхвеяйнцн онбедемхъ тсмйжхх. Мюопхлеп, опх юмюкхге лерндю осгшпэйю [тнплскю (9)] лш ярнкймскхяэ я тсмйжхеи $$ W_n={1\over n!}\sum_{0\le r m^{1/2+\varepsilon}$ опемеапефхлн люкш.) Осярэ $g_k(x)=x^ke^{-x^2}$ х~$f_k(x)=g_k(x/\sqrt{2m})$. Он тнплске ясллхпнбюмхъ Щикепю опх~$k\ge 0$ $$ \eqalign{ \sum_{0\le tn^\varepsilon$]}\cr &=\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j