\input style
%% 161
пРИВЕДЕННОЕ НИЖЕ РАССУЖДЕНИЕ ПОКАЖЕТ, ЧТО ЭТА ПОСЛЕДНЯЯ СУММА ЕСТЬ $O(1)$; 
СЛЕДОВАТЕЛЬНО, $U_n-T_n=O(1)$. (сМ. УПР.~47.)

дО СИХ ПОР МЫ ЕЩЕ НЕ ИСПОЛЬЗОВАЛИ НИКАКИХ МЕТОДОВ, КОТОРЫЕ БЫ 
ДЕЙСТВИТЕЛЬНО ОТЛИЧАЛИСЬ ОТ ПРИМЕНЯВШИХСЯ РАНЕЕ, НО
\picture{рИС. 20. кОНТУРЫ ИНТЕГРИРОВАНИЯ ДЛЯ ТОЖДЕСТВ С ГАММА-ФУНКЦИЯМИ.}
ДЛЯ ИЗУЧЕНИЯ РЯДА~$T_n$ ПОТРЕБУЕТСЯ НОВАЯ ИДЕЯ, ОСНОВАННАЯ НА ПРОСТЫХ 
ПРИНЦИПАХ ТЕОРИИ ФУНКЦИЙ КОМПЛЕКСНОГО ПЕРЕМЕННОГО. еСЛИ $x$---ПРОИЗВОЛЬНОЕ 
ПОЛОЖИТЕЛЬНОЕ ЧИСЛО, ТО
$$
e^{-x}={1\over 2\pi i}\int_{1/2-i\infty}^{1/2+i\infty} \Gamma(z)x^{-z}\,dz=
{1\over 2\pi}\int_{-\infty}^\infty\Gamma\left({1\over2}+it\right)x^{-(1/2+it)}\,dt.
\eqno(42)
$$
дЛЯ ДОКАЗАТЕЛЬСТВА ЭТОГО ТОЖДЕСТВА РАССМОТРИМ ПУТЬ ИНТЕГРИРОВАНИЯ, 
ПОКАЗАННЫЙ НА РИС.~20(a), ГДЕ $N$, $N'$ И $M$ ВЕЛИКИ. зНАЧЕНИЕ ИНТЕГРАЛА 
ВДОЛЬ ЭТОГО КОНТУРА РАВНО СУММЕ ВЫЧЕТОВ ВНУТРИ КОНТУРА, А ИМЕННО
$$
\sum_{0\le k<M} x^{-k}\lim_{z\to-k}(z+k)\Gamma(z)=
\sum_{0\le k<M} x^{-k}{(-1)^k\over k!}.
$$
иНТЕГРАЛ ПО ВЕРХНЕЙ ЧАСТИ КОНТУРА ЕСТЬ 
$O\left(\int_{-\infty}^{1/2}\abs{\Gamma(t+iN)}x^{-t}\,dt\right)$,
И У НАС ИМЕЕТСЯ ИЗВЕСТНАЯ ОЦЕНКА
$$
\Gamma(t+iN)=O(N^{t-1/2} e^{-\pi N/2}) \rem{ПРИ $N\to\infty$.}
$$
[сВОЙСТВА ГАММА-ФУНКЦИЙ СМ., НАПРИМЕР, В КНИГЕ A.~Erd\'elyi et al., Higher 
Transcendental Functions, 1 (New York: McGraw-Hill, 1953), ГЛ.~1.] пОЭТОМУ 
ИНТЕГРАЛ ПО ВЕРХНЕМУ ОТРЕЗКУ
БЕСКОНЕЧНО МАЛ: 
$O\left( e^{-\pi N/2}\int_{-\infty}^{1/2} (N/x)^t\,dt\right)$. 
иНТЕГРАЛ ПО НИЖНЕМУ
%% 162
ОТРЕЗКУ ВЕДЕТ СЕБЯ СТОЛЬ ЖЕ БЕЗОБИДНО. дЛЯ ВЫЧИСЛЕНИЯ ИНТЕГРАЛА ПО 
ЛЕВОМУ ОТРЕЗКУ КОНТУРА ВОСПОЛЬЗУЕМСЯ ТЕМ ФАКТОМ, ЧТО
$$
\eqalign{
\Gamma\left({1\over2}+it-M\right)&=
\Gamma\left({1\over2}+it\right)/\left(-M+{1\over2}+it\right)
  \ldots\left(-1+{1\over2}+it\right)=\cr
&=\Gamma\left({1\over2}+it\right) O(1/(M-1)!).\cr
}
$$
сЛЕДОВАТЕЛЬНО, ИНТЕГРАЛ ПО ЛЕВОЙ СТОРОНЕ ЕСТЬ 
$O(x^{M-1/2}/(M-1)!)\times
 \int_{-\infty}^\infty\abs{\Gamma\left({1\over2}+it\right)}\,dt$. 
пОЭТОМУ ПРИ $M$, $N$, $N'\to\infty$ УЦЕЛЕЕТ ЛИШЬ
ИНТЕГРАЛ ПО ПРАВОЙ СТОРОНЕ; ТЕМ САМЫМ ДОКАЗАНО ТОЖДЕСТВО (42). в 
ДЕЙСТВИТЕЛЬНОСТИ ТОЖДЕСТВО (42) ОСТАЕТСЯ В СИЛЕ И В ТОМ СЛУЧАЕ, ЕСЛИ 
ЗАМЕНИТЬ $1\over2$ ЛЮБЫМ ПОЛОЖИТЕЛЬНЫМ ЧИСЛОМ.

тЕМ ЖЕ САМЫМ РАССУЖДЕНИЕМ МОЖНО ВОСПОЛЬЗОВАТЬСЯ ДЛЯ ВЫВОДА ДРУГИХ 
ПОЛЕЗНЫХ СООТНОШЕНИЙ, СОДЕРЖАЩИХ ГАММА-ФУНКЦИИ. вЕЛИЧИНУ $x^{-z}$ МОЖНО 
ЗАМЕНИТЬ ДРУГИМИ ФУНКЦИЯМИ ОТ $z$; МОЖНО
ТАКЖЕ ЗАМЕНИТЬ ДРУГОЙ ВЕЛИЧИНОЙ КОНСТАНТУ $1\over2$. нАПРИМЕР,
$$
{1\over2\pi i}\int_{-3/2-i\infty}^{-3/2+i\infty}\Gamma(z)x^{-z}\,dz
=e^{-x}-1+x,
\eqno(43)
$$
А ЭТО---КРИТИЧЕСКАЯ ВЕЛИЧИНА В ФОРМУЛЕ (41) ДЛЯ $T_n$:
$$
T_n=n\sum_{j\ge1}
{1\over2\pi i}\int_{-3/2-i\infty}^{-3/2+i\infty}\Gamma(z)(n/2^j)^{-1-z}\,dz.
\eqno(44)
$$

сУММИРОВАНИЕ МОЖНО ВНЕСТИ ПОД ЗНАК ИНТЕГРАЛА, ТАК КАК СХОДИМОСТЬ ЗДЕСЬ 
ДОСТАТОЧНО ХОРОШАЯ; ИМЕЕМ
$$
\sum_{j\le 1}(n/2^j)^w=n^w\sum_{j\le1}(1/2^w)^j=n^w/(2^w-1),
\rem{ЕСЛИ $\Re(w)>0$,}
$$
ТАК КАК $\abs{2^w} = 2^{\Re(w)} > 1$. пОЭТОМУ
$$
T_n={n\over2\pi i}
\int_{-3/2-i\infty}^{-3/2+i\infty}
 {\Gamma(z)n^{-1-z}\over 2^{-1-z}-1}\, dz,
\eqno(45)
$$
И ОСТАЕТСЯ ОЦЕНИТЬ ПОСЛЕДНИЙ ИНТЕГРАЛ.

нА ЭТОТ РАЗ ИНТЕГРИРОВАНИЕ ПРОИЗВОДИТСЯ ПО КОНТУРУ, КОТОРЫЙ БОЛЬШЕ 
ВЫТЯНУТ ВПРАВО, КАК ИЗОБРАЖЕНО НА РИС. 20(b).
%% 163
иНТЕГРАЛ ПО ВЕРХНЕМУ ОТРЕЗКУ ЕСТЬ 
$O\left(n^{1/2}e^{-\pi M/2} \int_{-3/2}^M N^t\,dt\right)$,
ЕСЛИ $2^{iN}\ne1$, А ИНТЕГРАЛ ПО НИЖНЕМУ ОТРЕЗКУ ТАКЖЕ ПРЕНЕБРЕЖИМО   
МАЛ.   иНТЕГРАЛ   ПО   ПРАВОМУ  ОТРЕЗКУ   РАВЕН
$O\left( n^{-1-M} \int_{-\infty}^\infty \abs{\Gamma(M+it)}\,dt\right)$. 
фИКСИРУЯ $M$ И УСТРЕМЛЯЯ $N$, $N'$ К~$\infty$,
МОЖНО ПОКАЗАТЬ, ЧТО $-T_n/n$ ЕСТЬ $O(n^{-1-M})$ ПЛЮС СУММА ВЫЧЕТОВ В 
ОБЛАСТИ $-3/2 < \Re(z)<M$. пУСТЬ $M\to\infty$, $\Gamma(z)$ ИМЕЕТ ПРОСТЫЕ 
ПОЛЮСЫ ПРИ $z=-1$ И~$z=0$, $n^{-1-z}$ НЕ ИМЕЕТ ПОЛЮСОВ, a~$1/(2^{-1-z}-1)$ 
ИМЕЕТ ПРОСТЫЕ ПОЛЮСЫ ПРИ $z=-1+2\pi i k/\ln2$.

нАИБОЛЬШУЮ ТРУДНОСТЬ ПРЕДСТАВЛЯЕТ ДВОЙНОЙ ПОЛЮС В ТОЧКЕ~$z=-1$. еСЛИ 
$w=z+1$ МАЛО, ТО МОЖНО ВОСПОЛЬЗОВАТЬСЯ ИЗВЕСТНЫМ СООТНОШЕНИЕМ
$$
\Gamma(z+1)
=\exp(-\gamma z+\zeta(2)z^2/2-\zeta(3)z^3/3+\zeta(4)z^4/4-\ldots),
$$
ГДЕ~$\zeta(s)=1^{-s}+2^{-s}+3^{-s}+\ldots=H_\infty^{(s)}$, ДЛЯ ВЫВОДА 
СЛЕДУЮЩИХ РАЗЛОЖЕНИЙ:
$$
\eqalign{
\Gamma(z)&={\Gamma(w+1)\over w(w-1)}=-w^{-1}+(\gamma-1)+O(w);\cr
n^{-1-z}&=1-(\ln n)w+O(w^2);\cr
1/(2^{-1-z}-1)&=-w^{-1}/\ln2-{1\over2}+O(w).\cr
}
$$
вЫЧЕТ В ТОЧКЕ~$z=-1$ РАВЕН КОЭФФИЦИЕНТУ ПРИ $w^{-1}$ В ПРОИЗВЕДЕНИИ ЭТИХ 
ТРЕХ ФОРМУЛ, А ИМЕННО ${1\over2}-(\ln n+\gamma-1)/\ln2$. пРИБАВЛЯЯ 
ОСТАЛЬНЫЕ ВЫЧЕТЫ, ПОЛУЧАЕМ ФОРМУЛУ
$$
T_n/n={\ln n+\gamma-1\over \ln 2}-{1\over2}+f(n)+{2\over n},
\eqno(46)
$$
ГДЕ  $f(n)$---ФУНКЦИЯ ДОВОЛЬНО НЕОБЫЧНОГО ВИДА:
$$
f(n)={2\over\ln 2}
\sum_{k\ge1} \Re(\Gamma(-1-2\pi ik/\ln2)\exp(2\pi i k\log_2n)).
\eqno(47)
$$
зАМЕТИМ, ЧТО $f(n)=f(2n)$. сРЕДНЕЕ ЗНАЧЕНИЕ $f(n)$ РАВНО~0, ТАК КАК 
СРЕДНЕЕ ЗНАЧЕНИЕ КАЖДОГО СЛАГАЕМОГО РАВНО 0. (мОЖНО СЧИТАТЬ, ЧТО 
ВЕЛИЧИНА $(\log_2 n) \bmod 1$ РАСПРЕДЕЛЕНА РАВНОМЕРНО, ПРИНИМАЯ ВО 
ВНИМАНИЕ РЕЗУЛЬТАТЫ О ЧИСЛАХ С ПЛАВАЮЩЕЙ ТОЧКОЙ, ПОЛУЧЕННЫЕ В П.~4.2.4.) 
кРОМЕ ТОГО, ПОСКОЛЬКУ 
$\abs{\Gamma(-1+it)}=\abs{\pi/(t(1+t^2)\sinh \pi t)}^{1/2}$, НЕТРУДНО 
ПОКАЗАТЬ, ЧТО
$$
f(n)< 0.0000001725;
$$
ТАКИМ ОБРАЗОМ, В ПРАКТИЧЕСКИХ ПРИЛОЖЕНИЯХ $f(n)$ МОЖНО СПОКОЙНО 
ОТБРОСИТЬ. чТО КАСАЕТСЯ ТЕОРИИ, ТО БЕЗ~$f(n)$ МЫ НЕ МОЖЕМ
%%164
ПОЛУЧИТЬ АСИМПТОТИЧЕСКОГО РЯДА ДЛЯ $U_n$; ИМЕННО ПОЭТОМУ ВЕЛИЧИНА~$U_n$ 
СРАВНИТЕЛЬНО ТРУДНА ДЛЯ АНАЛИЗА. 
иТАК, МЫ ДОКАЗАЛИ, ЧТО
$$
U_n=n\log_2n+n\left({\gamma-1\over\ln2}-{1\over2}+f(n)\right)+O(1).
\eqno(48)
$$
дРУГИЕ ПРИМЕРЫ ПРИМЕНЕНИЯ ЭТОГО МЕТОДА ГАММА-ФУНКЦИЙ МОЖНО НАЙТИ В 
УПР.~51--53 И В \S~6.3.

\excercises
\ex[м20] пУСТЬ $a_1$ \dots $a_n$---ПЕРЕСТАНОВКА МНОЖЕСТВА $\{1, \ldots, n\}$, 
И ПУСТЬ $i$ И $j$ ТАКОВЫ, ЧТО $i<j$ И~$a_i>a_j$. пУСТЬ $a'_1$ \dots 
$a'_n$---ПЕРЕСТАНОВКА, КОТОРАЯ ПОЛУЧАЕТСЯ ИЗ $a_1$ \dots $a_n$, ЕСЛИ 
ПОМЕНЯТЬ МЕСТАМИ $a_i$ И $a_j$. мОЖЕТ ЛИ В $a'_1$ \dots $a'_n$ БЫТЬ БОЛЬШЕ 
ИНВЕРСИЙ, ЧЕМ В $a_1$ \dots $a_n$?

\rex[м25] (a) кАКОВО МИНИМАЛЬНОЕ ЧИСЛО ОБМЕНОВ, НЕОБХОДИМОЕ ДЛЯ ТОГО,
 ЧТОБЫ ОТСОРТИРОВАТЬ ПЕРЕСТАНОВКУ 3\ 7\ 6\ 9\ 8\ 1\ 4\ 5? (b) вООБЩЕ ПУСТЬ 
ДАНА ПЕРЕСТАНОВКА $\pi=a_1\ \ldots\ a_n$ МНОЖЕСТВА $\{1, \ldots, n\}$, И 
ПУСТЬ 
$\mathop{\rm xch}\nolimits (\pi)$---МИНИМАЛЬНОЕ ЧИСЛО ОБМЕНОВ, В РЕЗУЛЬТАТЕ 
КОТОРЫХ ПЕРЕСТАНОВКА $\pi$ БУДЕТ ОТСОРТИРОВАНА В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. 
вЫРАЗИТЕ $\mathop{\rm xch}\nolimits (\pi)$, ЧЕРЕЗ "БОЛЕЕ ПРОСТЫЕ" 
ХАРАКТЕРИСТИКИ ПЕРЕСТАНОВКИ~$\pi$. (сР. С УПР. 5 2.1--39.)

\ex[10] яВЛЯЕТСЯ ЛИ УСТОЙЧИВОЙ СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА (АЛГОРИТМ B)?

\ex[м23] еСЛИ В ШАГЕ B4 ПОЛУЧИТСЯ $t=1$, ТО НА САМОМ ДЕЛЕ РАБОТУ 
АЛГОРИТМА~B МОЖНО СРАЗУ ЖЕ ЗАКАНЧИВАТЬ, ПОТОМУ ЧТО В СЛЕДУЮЩЕМ ШАГЕ B2 
НЕ ВЫПОЛНИТСЯ НИКАКИХ ПОЛЕЗНЫХ ДЕЙСТВИЙ. кАКОВА ВЕРОЯТНОСТЬ ТОГО, ЧТО 
ПРИ СОРТИРОВКЕ СЛУЧАЙНОЙ ПЕРЕСТАНОВКИ В ШАГЕ B4 ОКАЖЕТСЯ $t=1$?

\ex[м25] пУСТЬ $b_1$ $b_2$ \dots $b_n$---ТАБЛИЦА ИНВЕРСИЙ ПЕРЕСТАНОВКИ $a_1$ 
$a_2$ \dots $a_n$. пОКАЖИТЕ, ЧТО ПОСЛЕ $r$ ПРОСМОТРОВ СОРТИРОВКИ МЕТОДОМ 
ПУЗЫРЬКА ЗНАЧЕНИЕ ПЕРЕМЕННОЙ |BOUND| РАВНО $\max \{b_i+i \mid b_i\ge 
r\}-r$, ГДЕ 
$0\le r\le \max(b_1, \ldots, b_n)$.

\ex[м22] пУСТЬ $a_1$ \dots{} $a_n$---ПЕРЕСТАНОВКА МНОЖЕСТВА $\{1, \dots, 
n\}$, И ПУСТЬ $a'_1$ \dots{} $a'_n$---ОБРАТНАЯ К НЕЙ ПЕРЕСТАНОВКА. пОКАЖИТЕ, 
ЧТО ЧИСЛО ПРОСМОТРОВ, НЕОБХОДИМЫХ ДЛЯ ТОГО, ЧТОБЫ ОТСОРТИРОВАТЬ $a_1$ 
\dots{} $a_n$" МЕТОДОМ ПУЗЫРЬКА. РАВНО $1+\max(a'_1-1, a'_2-2, \ldots, a'_n-n)$.

\ex[м28] вЫЧИСЛИТЕ СТАНДАРТНОЕ ОТКЛОНЕНИЕ ЧИСЛА ПРОСМОТРОВ 
СОРТИРОВКИ МЕТОДОМ ПУЗЫРЬКА И ВЫРАЗИТЕ ЕГО ЧЕРЕЗ $n$ И ФУНКЦИЮ $P(n)$. [сР.
 С ФОРМУЛАМИ (6) И (7).]

\ex[м24] вЫВЕДИТЕ ФОРМУЛУ (8).

\ex[м48] пРОАНАЛИЗИРУЙТЕ ЧИСЛО ПРОСМОТРОВ И ЧИСЛО СРАВНЕНИЙ В АЛГОРИТМЕ 
ШЕЙКЕР-СОРТИРОВКИ. (\emph{зАМЕЧАНИЕ:} ЧАСТИЧНАЯ ИНФОРМАЦИЯ СОДЕРЖИТСЯ В 
УПР. 5.4.8--9.)

\ex[м26] пУСТЬ $a_1$ $a_2$ \dots{} $a_n$---2-УПОРЯДОЧЕННАЯ ПЕРЕСТАНОВКА 
МНОЖЕСТВА  $\{1, 2, \ldots, n\}$. (a) кАКОВЫ КООРДИНАТЫ КОНЕЧНЫХ ТОЧЕК 
$a_i\hbox{-ГО}$ 
ШАГА СООТВЕТСТВУЮЩЕГО РЕШЕТОЧНОГО ПУТИ 
(СР. С РИС.~11)? (b) дОКАЖИТЕ, ЧТО СРАВНЕНИЕ/ОБМЕН
ЭЛЕМЕНТОВ $a_1$: $a_2$, $a_3$, $a_4$, \dots СООТВЕТСТВУЕТ ПЕРЕГИБАНИЮ ПУТИ ОТНОСИТЕЛЬНО
ДИАГОНАЛИ, КАК НА РИС.~18(b). (С) дОКАЖИТЕ, ЧТО СРАВНЕНИЕ/ОБМЕН ЭЛЕМЕНТОВ
$a_2$: $a_{2+d}$, $a_4$:$a_{4+d}$, \dots{} СООТВЕТСТВУЕТ ПЕРЕГИБАНИЮ ПУТИ 
ОТНОСИТЕЛЬНО ЛИНИИ, 
РАСПОЛОЖЕННОЙ НА $m$ ЕДИНИЦ НИЖЕ ДИАГОНАЛИ, КАК НА РИС. 18(С), (d) И (e), ЕСЛИ
$d=2m-l$.

\rex[м25] нА КАКОЙ ПЕРЕСТАНОВКЕ МНОЖЕСТВА $\{1, 2, \ldots, 16\}$ 
ДОСТИГАЕТСЯ МАКСИМУМ ЧИСЛА ОБМЕНОВ В АЛГОРИТМЕ бЭТЧЕРА?

\ex[24] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА M, ПРЕДПОЛАГАЯ, 
ЧТО \MIX---ДВОИЧНАЯ ВЫЧИСЛИТЕЛЬНАЯ МАШИНА С ОПЕРАЦИЯМИ |AND| И |SRB|. 
сКОЛЬКО ВРЕМЕНИ ПОТРЕБУЕТСЯ ВАШЕЙ ПРОГРАММЕ, ЧТОБЫ ОТСОРТИРОВАТЬ 
ШЕСТНАДЦАТЬ ЗАПИСЕЙ ИЗ ТАБЛ.~1?
%%165

\ex [10] уСТОЙЧИВА ЛИ СОРТИРОВКА бЭТЧЕРА?

\ex [м21] пУСТЬ $c(N)$---ЧИСЛО СРАВНЕНИЙ КЛЮЧЕЙ, ПРОИЗВОДИМЫХ ПРИ 
СОРТИРОВКЕ $N$ ЭЛЕМЕНТОВ МЕТОДОМ бЭТЧЕРА; ЭТО РАВНО ЧИСЛУ ВЫПОЛНЕНИИ 
ШАГА M4.
(a) пОКАЖИТЕ, ЧТО ПРИ $t\ge 1$ $c(2^t)=2c(2^{t-1}+(t-1)2^{t-1}+1.$
(b) нАЙДИТЕ ПРОСТОЕ ВЫРАЖЕНИЕ ДЛЯ $c(2^t)$ КАК ФУНКЦИЮ ОТ~$t$. 
(\emph{уКАЗАНИЕ:} РАССМОТРИТЕ ПОСЛЕДОВАТЕЛЬНОСТЬ $x_t=c(2^t)/2^t)$.

\ex[м38] сОДЕРЖАНИЕ ЭТОГО УПРАЖНЕНИЯ---АНАЛИЗ ФУНКЦИИ $c(N)$ ИЗ УПР.~14
И НАХОЖДЕНИЕ ФОРМУЛЫ ДЛЯ $c(N)$, ЕСЛИ $N=2^{e_1}+2^{e_2}+\cdots+2^{e_r}$, 
$e_1>e_2>\ldots>e_r\ge0$. (a) пУСТЬ $a(N)=c(N+1)-c(N)$. дОКАЖИТЕ, ЧТО 
$a(2n)=a(n)+\floor{\log_2(2n)}$, $a(2n+1)=a(n)+1$;  ОТСЮДА
$$
a(N)=\perm{e_1+1}{2}-r(e_1-1)+(e_1+e_2+\cdots+e_r).
$$
(b) пУСТЬ $x(n)=a(n)-a(\floor{n/2})$,  И ТОГДА  
$a(n)=x(n)+x(\floor{n/2})+x(\floor{n/4})+\cdots$. пУСТЬ 
$y(n)=x(1)+x(2)+\cdots+x(n)$, И 
ПУСТЬ~$z(2n)=y(2n)-a(n)$, $z(2n+1)=y(2n+1)$.  дОКАЖИТЕ, ЧТО 
$c(N+1)=z(N)+2z(\floor{N/2})+4z(\floor{N/4})+\cdots$. (c) дОКАЖИТЕ,ЧТО 
$y(N)=N+(\floor{N/2}+1)\times(e_1-1)-2^{e_1}+2$. (d) тЕПЕРЬ СОБЕРИТЕ ВСЕ 
ВМЕСТЕ И НАЙДИТЕ ВЫРАЖЕНИЕ $c(N)$ ЧЕРЕЗ ПОКАЗАТЕЛИ $e_j$ ПРИ ФИКСИРОВАННОМ 
ЗНАЧЕНИИ $r$.

\ex[вм46] нАЙДИТЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ СРЕДНЕГО ЧИСЛА ОБМЕНОВ В СЛУЧАЕ,
 КОГДА АЛГОРИТМ бЭТЧЕРА ПРИМЕНЯЕТСЯ К $N=2^t$ РАЗЛИЧНЫМ ЭЛЕМЕНТАМ, 
РАСПОЛОЖЕННЫМ В СЛУЧАЙНОМ ПОРЯДКЕ.

\rex[20] гДЕ В АЛГОРИТМЕ Q ИСПОЛЬЗУЕТСЯ ТО, ЧТО $K_0$ И~$K_{N+1}$ 
ОБЛАДАЮТ ЗНАЧЕНИЯМИ, ПОСТУЛИРОВАННЫМИ НЕРАВЕНСТВАМИ (13)?

\rex[20] оБ®ЯСНИТЕ, КАК РАБОТАЕТ АЛГОРИТМ Q В СЛУЧАЕ, КОГДА ВСЕ КЛЮЧИ В 
ИСХОДНОМ ФАЙЛЕ РАВНЫ. чТО ПРОИЗОЙДЕТ, ЕСЛИ В ШАГАХ Q3 И Q5 ЗАМЕНИТЬ ЗНАКИ 
"$<$" НА "$\le$"?

\ex[15] бУДЕТ ЛИ АЛГОРИТМ Q ПО-ПРЕЖНЕМУ РАБОТАТЬ ПРАВИЛЬНО, ЕСЛИ ВМЕСТО 
СТЕКА (ПОСЛЕДНИМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ) ВОСПОЛЬЗОВАТЬСЯ ОЧЕРЕДЬЮ 
(ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ)?

\ex[м20] вЫРАЗИТЕ НАИБОЛЬШЕЕ ЧИСЛО ЭЛЕМЕНТОВ, КОТОРЫЕ МОГУТ ОДНОВРЕМЕННО 
ОКАЗАТЬСЯ В СТЕКЕ ВО ВРЕМЯ РАБОТЫ АЛГОРИТМА Q, В ВИДЕ ФУНКЦИИ ОТ~M И~$N$.

\ex[20] оБ®ЯСНИТЕ, ПОЧЕМУ ФАЗА РАЗДЕЛЕНИЯ В АЛГОРИТМЕ Q ТРЕБУЕТ КАК РАЗ 
ТАКОГО ЧИСЛА СРАВНЕНИЙ, ПЕРЕСЫЛОК И Т. Д., КАК ЭТО ОПИСАНО В (17).

\ex[м25] пУСТЬ $p_kN$---ВЕРОЯТНОСТЬ ТОГО, ЧТО ВЕЛИЧИНА~$A$ В (14) 
БУДЕТ РАВНА~$k$, ЕСЛИ АЛГОРИТМ Q ПРИМЕНЯЕТСЯ К СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ МНОЖЕСТВА
$\{1, 2, \ldots, N\}$, И ПУСТЬ~$A_N(z)=\sum_k p_kN^{z^k}$---СООТВЕТСТВУЮЩАЯ 
ПРОИЗВОДЯЩАЯ ФУНКЦИЯ.   дОКАЖИТЕ,   ЧТО~$A_N(z)=1$   ПРИ~$N\le M$,   
И~$A_N(z)= z(\sum_{1\le s\le N} A_{s-1}(z)A_{N-s}(z))/N$ ПРИ~$N>M$. 
нАЙДИТЕ АНАЛОГИЧНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ, ОПРЕДЕЛЯЮЩИЕ ДРУГИЕ 
РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ $B_N(z)$, $C_N(z)$, $D_N(z)$, $E_N(z)$, 
$L_N(z)$, $X_N(z)$.

\ex[м24] пУСТЬ $A_N$, $B_N$, $D_N$, $E_N$, $L_N$, $X_N$---СРЕДНИЕ ЗНАЧЕНИЯ 
СООТВЕТСТВУЮЩИХ ВЕЛИЧИН В (14) ПРИ СОРТИРОВКЕ СЛУЧАЙНОЙ 
ПЕРЕСТАНОВКИ-МНОЖЕСТВА $\{1, 2, \ldots, N\}$. нАЙДИТЕ ДЛЯ ЭТИХ ВЕЛИЧИН 
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ, АНАЛОГИЧНЫЕ (18), ЗАТЕМ РАЗРЕШИТЕ ЭТИ 
СООТНОШЕНИЯ И ПОЛУЧИТЕ ФОРМУЛЫ (25).

\ex[м21] оЧЕВИДНО, В АЛГОРИТМЕ Q ПРОИЗВОДИТСЯ НЕСКОЛЬКО БОЛЬШЕ СРАВНЕНИЙ, 
ЧЕМ ЭТО НЕОБХОДИМО, ПОТОМУ ЧТО В ШАГАХ Q3 И Q5 МОЖЕТ ОКАЗАТЬСЯ, ЧТО $i=j$ 
ИЛИ ДАЖЕ $i>j$. сКОЛЬКО СРАВНЕНИЙ $G_N$ ПРОИЗВОДИЛОСЬ БЫ В СРЕДНЕМ, ЕСЛИ 
БЫ ИСКЛЮЧАЛИСЬ ВСЕ СРАВНЕНИЯ ПРИ $i\ge j$?

\ex[м20] чЕМУ РАВНЫ ТОЧНЫЕ ЗНАЧЕНИЯ ВЕЛИЧИН $A$, $B$, $C$, $D$, $E$, $L$, 
$X$ ДЛЯ ПРОГРАММЫ Q В СЛУЧАЕ, КОГДА ИСХОДНЫЕ КЛЮЧИ ПРЕДСТАВЛЯЮТ СОБОЙ 
УПОРЯДОЧЕННЫЙ НАБОР ЧИСЕЛ $1$, $2$, \dots, $N$ В ПРЕДПОЛОЖЕНИИ, ЧТО $N>M$? 
\rex[M2I] пОСТРОЙТЕ ИСХОДНЫЙ ФАЙЛ, ПРИ КОТОРОМ ПРОГРАММА Q .РАБОТАЛА БЫ 
ЕЩЕ МЕДЛЕННЕЕ, ЧЕМ В УПР.~25. (пОПЫТАЙТЕСЬ НАЙТИ ДЕЙСТВИТЕЛЬНО ПЛОХОЙ СЛУЧАЙ.)

%% 166
\bye