Нижняя граница сложности в среднем

При рассмотрении сложности в среднем мы основываемся на тех же понятиях нижней границы, оптимального и оптимального по порядку сложности алгоритма, которые были введены для сложности в худ­шем случае.

Пример 17.1. Вновь обратимся к классу алгоритмов сортировки. Будем, как и в § 6, рассматривать вероятностное пространство П _n.

Предложение 17.1. Функция log₂ n! является нижней границей сложности в среднем для класса алгоритмов сортировки массивов длины n с помощью сравнений.

§ 17. Нижняя граница сложности в среднем

Прежде всего докажем вспомогательное утверждение.

Лемма 17.1. В любом двоичном дереве с т листьями сумма высот всех листьев не меньше т log₂ т.

Доказательство. Пусть непусто множество М всех двоичных дере­вьев, для которых сумма высот всех листьев меньше т log₂ т. Выбе­рем в М какое-нибудь из деревьев, имеющих наименьшую сумму вы­сот, и обозначим его U (сумму высот всех листьев будем обозначать через Я(J7)). Это дерево не может состоять из одного лишь корня, потому что для такого дерева обсуждаемое неравенство выполнено. Далее, из корня этого дерева не может выходить только одно ребро, потому что для дерева, получающегося из исходного удалением кор­ня и этого ребра, обсуждаемое неравенство не выполняется, и такое новое дерево имеет сумму высот меньшую, чем дерево U (противо­речие со способом выбора дерева U). Поэтому из корня дерева U выходит два ребра, концы которых являются корнями двух деревьев и_г и U₂, для которых выполнено обсуждаемое неравенство. Пусть эти деревья имеют, соответственно, т_г и т₂ листьев, т_ъ т₂ > 0. Имеем соотношение для сумм высот всех листьев

H{U) =H(U₁) + Я(!У₂) + т^т_г log₂ т_г + т₂ log₂ m ₂ + т.

Отсюда получаем

Я([7) =г т_г log₂ т_г + {т- т_г) log₂(m-т_г)+т

при некотором т_г таком, что 1 ^ т_г ^ т - 1.

Легко показать, что при фиксированном т функция /(х) =х log₂ х+ + (т-х) log₂(m - x) достигает минимума на отрезке [1, т - 1] в точке (не обязательно целой) т/2. Поэтому

Я([7) ^ j log₂ j + j log₂ Щ-+т = т log₂ т.
Но это противоречит способу выбора U. Лемма доказана. □

Доказательство предложения 17.1. Рассмотрим какое-либо дерево сортировки массива длины п. Это дерево имеет ровно п! листьев, каждый лист соответствует перестановке элементов исходного масси­ва. Появление на выходе рассматриваемой сортировки любой из этих

1 перестановок имеет одну и ту же вероятность —, количество сравне­ний, приводящее к этой перестановке—это высота соответствующего этой перестановке листа. Поэтому математическое ожидание числа

сравнений равно произведению суммы высот всех листьев на —.

120 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

Согласно лемме 17.1 сумма высот всех листьев должна быть не
меньше, чем n\ log₂ n\. Отсюда математическое ожидание числа срав­
нений не меньше, чем log₂ n\. □

Доказанные ранее теорема 16.2 и предложение 16.1 справедливы в равной мере и для сложности в худшем случае, и для сложности в среднем. Принимая это во внимание, мы получаем следствие пред­ложения 17.1:

Сортировка бинарными вставками и сортировка фон Неймана, а также быстрая сортировка являются оптимальными по порядку сложности в среднем по числу сравнений.

К этому списку позднее мы добавим и рекурсивную сортиров­ку слияниями. Наиболее же существенно упоминание в этом списке быстрой сортировки. С одной стороны, как мы знали и раньше, эта сортировка очень удобна и имеет низкую пространственную слож­ность, с другой—мы видим теперь, что и в смысле временной слож­ности в среднем эта сортировка в определенном смысле может быть отнесена к наилучшим.

Можно показать существование оптимальной в среднем сортиров­ки: для каждого фиксированного n в множестве всех деревьев сорти­ровки массивов длины n можно рассмотреть подмножество деревьев, имеющих наименьшую сумму H высот всех листьев (тогда и H/n\ будет иметь наименьшее значение), и взять какое-нибудь из дере­вьев этого подмножества. Определяя сортировку этим способом для всех n мы получаем оптимальную сортировку. Для любой оптималь­ной в среднем сортировки выполнено

T _opt(n)~log₂ n!~ n log₂ n,

так как, например, мы имеем T _vN(n)~log₂ n! и

T _vN(n) ^ T _vN(n) ^ T (n) ^ log₂ n\.

В этом примере, как и во всем этом параграфе, мы не касаемся рандомизированных алгоритмов, о которых будет говориться в § 18.

Как мы ранее наблюдали в некоторых примерах, рассмотрение функции L, подобранной надлежащим образом, и изучение измене­ния ее значений в ходе выполнения алгоритма нередко позволяет получать хорошие оценки (в частности, нижние границы) сложности в худшем случае. Рассмотрение такого рода функций может приво­дить к цели и при исследовании сложности в среднем. В задаче 37 функцию L можно определить как максимум значений компонент

§ 17. Нижняя граница сложности в среднем

инверсионного вектора перестановки. Эта функция является случай­ной величиной на П _n, при этом Д L = -1 на каждом шаге алгоритма. В других ситуациях начальное значение L может определяться одно­значно, тогда как Д L является случайной величиной. Сформулируем теорему, полезную в этих ситуациях.

Теорема 17.1. Пусть £ ₁, £₂,... —последовательность неотрица­тельных случайных величин на некотором вероятностном простран­стве. Пусть числовая последовательность h ₁, h₂,... такова, что для каждого k ^1 выполнено E (C _k l^ 1,?₂,...,? k -1) ** h при всех значениях?₁,?2,..., S _k -1. Зафиксируем неотрицательное число q и введем цело­численную случайную величину

т = min n:

7-------- Л

k =1

Пусть т < оо всюду на рассматриваемом вероятностном простран­стве. Тогда е(£ h_k ^ q.

k =1

Доказательство приведено в приложении E.

Для того чтобы воспользоваться этой теоремой, можно опять по­пытаться определить некоторую неотрицательную функцию L, отра­жающую степень «недорешенности» рассматриваемой задачи: значе­ние L равно нулю, если алгоритм доработал до конца и задача ре­шена. Считаем, что всем входам фиксированного размера сопостав­ляется одно и то же значение функции L. После выбора такой функ­ции L мы должны показать, что последовательность величин Е(-Д L), соответствующих идущим друг за другом этапам алгоритма, огра­ничена сверху некоторой известной числовой последовательностью h₁,h2,...; тогда случайная величина т, равная для данного входа об­щему количеству этапов, приводящих к завершению алгоритма, та­кова, что Е(2 hk ) ^ q, где q — значение функции L, сопоставляе-

мое входам алгоритма рассматриваемого фиксированного размера. Это неравенство можно использовать, чтобы оценить снизу значение Ет. Конечность величины т следует из завершимости алгоритма для любого входа.

Пример 17.2. Вернемся к задаче одновременного выбора наиболь­шего и наименьшего элементов массива длины n, n ^ 2, с помощью сравнений (пример 15.1). Вероятностным пространством здесь вновь будем считать П _n. Каждая перестановка из П _n отражает, как обычно,

122 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

взаимный порядок элементов исходного массива. Все перестановки считаются равновероятными.

Чтобы воспользоваться теоремой 17.1, мы полагаем, что случай­ные величины Е,₁, Е,₂,... для произвольного алгоритма одновременно­го выбора наибольшего и наименьшего элементов равны значениям -AL на последовательных шагах этого алгоритма, об определении функции L будет сказано ниже. Значения £ ₁, £₂,... зависят от кон­кретной перестановки из П _n, отражающей взаимный порядок элемен­тов в исходном массиве. После того, как алгоритм закончил работу, значения Е,_k при последующих значениях k равны нулю.

Предложение 17.2. Функция

(

-n - 2, если n четно,

3 1 (17.1)

I 2n - 2 + _{2 n}-, если n нечетно,

является нижней границей сложности в среднем алгоритмов одновре­менного выбора наибольшего и наименьшего элементов массива дли­ны n, n ^ 2, c помощью сравнений.

Доказательство. Вновь обратимся к множествам A, B, C, D, к рас­смотренным в доказательстве предложения 15.1 типам AA,AB,...,DD сравнений, количествам a, b, c, d элементов множеств A, B,C,Dи функ­ции L(a, b, c, d) = ³₂ a + b + c - 2 (равенство L = 0 является необходимым и достаточным условием того, что искомые элементы найдены).

Пусть в процессе выбора наибольшего и наименьшего элементов массива уже произведены некоторые сравнения элементов этого мас­сива. При каждом из этих сравнений получался некоторый результат «истина» или «ложь», и эти результаты нам известны. Если процесс выбора наибольшего и наименьшего элементов еще не завершен, то следующим шагом вновь будет некоторое сравнение одного из типов AA, AB,..., DD. Сравнения AB, AC и BC представляют особый интерес, так как можно бы предположить, что здесь получится ЕД L< -1. Но на самом деле это неравенство не имеет места ни при одном из этих трех типов сравнений.

Тип BC. Покажем невозможность такого выбора индексов i и j, основанного только на результатах уже произведенных сравнений, что x_i g B, xj g C и при этом с вероятностью, не меньшей половины, выполняется x_i < x_j.

Пусть сделан некий выбор индексов i и j, при котором x_i е B, xj g C. Рассмотрим множество M всех массивов y ₁ ,y₂,...,y_n, которые

§ 17. Нижняя граница сложности в среднем

получаются перестановками элементов массива х ₁, х₂,...,х_п и при этом сравнения элементов с теми же самыми индексами, которые использовались в уже произведенных сравнениях элементов массива х ₁, х₂,...,х_п, дают для массивов из М результаты, совпадающие с по­лученными для х ₁, х₂,...,х_п. Представим множество М в виде объеди­нения двух непересекающихся подмножеств М ₁ и М₂, где в М ₁ вхо­дят те массивы, для которых у < у_;-, а в М₂—те, для которых у,- < у. Покажем, что в М ₁ больше элементов, чем в М₂. Операция обмена у <—>у_;- определяет взаимно однозначное отображение на себя мно­жества всех массивов, которые получаются перестановками элемен­тов массива х ₁ ,х₂,...,х_п. Обратным к этому отображению является оно само. В силу определения множеств В и С это отображение пе­реводит элементы множества М₁ в элементы множества М₂. Следова­тельно, в М ₁ элементов не больше, чем в М₂. Но в М₂ найдется мас­сив, который при этом отображении не переходит в массив из М₁ и, более того, вообще покидает множество М (чтобы убедиться в этом, достаточно заметить, что в М₂ имеется такой массив У ₁ ,у₂,...,у_п, для которого yj = тт{у ₁ ,у₂,...,у„}). Поэтому в М ₁ элементов меньше, чем в М₂. Если т₁, т₂ обозначают количества элементов множеств М ₁ и М₂, то имеем

— < —

т₁+т₂ т₁ + т₂

и, следовательно,

m 1 1

— <.

т₁+т₂ 2

Таким образом, вероятность того, что i -й элемент меньше j -го, есть ¹₂ - е, е > 0. Получаем

ЕД1 = -2¹₂ - е) = -1 + 2е > -1.

Тип АВ. Аналогично предыдущему можно показать, что при лю­бом способе выбора индексов таких, что х_{ е А, х_;- е В, вероятность

выполнения неравенства x_t > х_;- есть - - е, е > 0. Получаем

ЕД1 = -!(¹₂-е) -1(1+_е)=-1 + е > -1.

Тип АС. Рассматривается аналогично типу АВ.

В дальнейшем будет полезна оценка е для сравнений типов АВ и АС. Рассмотрим для определенности АВ. Очевидно, что чем больше сравнений к рассматриваемому моменту прошел элемент х_;- е В, тем меньше вероятность того, что элемент x_teA окажется больше него.

124 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

Наибольшая же вероятность получится в случае, когда х_;- сравнивал­ся только с одним элементом, например с x_s, и x_s —это наименьший элемент исходного массива. Вычислим вероятность, с которой в этом случае x_t>Xj. Итак, если упорядочить все элементы, кроме x, Xj, то x_s окажется наименьшим (первым). Общее число способов, которыми к этой упорядоченной совокупности можно добавить x, Xj, с учетом x_s < xj равно n (n - 2) (для добавления _Xj существует п - 2 способа, за­тем добавляем x, и для этого существует п способов). Из них ₂) - 1 соответствуют неравенству x_t < x_i (возможен любой выбор двух среди п мест, кроме двух первых). Интересующая нас вероятность равна

п(п-2)-(^п) + 1 1 1

■ ■

п(п-2) 2 2п

Это дает нам е ^ 1-, и, таким образом,

для АВ и АС. Если при четном п удастся обойтись сравнениями ти­пов АА,ВВ,СС, то сравнений потребуется в точности ³₂п-2. Если п нечетно, то для решения задачи обязательно потребуется произве­сти хотя бы одно сравнение типа АВ, АС или AD. Сравнение типа AD

дает Д1 = -¹₂ > -1 + ₂¹.

Можно убедиться и в том, что для сравнений типов АВ и АС выполняется ЕД1^-1 + —, если ЕД1 рассматривается как матема­тическое ожидание при условии, что значения Д1 для всех преды­дущих сравнений, предписываемых алгоритмом, известны. Эти из­вестные значения определяют некоторое событие V в вероятност­ном пространстве П„. Событие V может быть представлено как сум­ма V₁ + V₂ +... + V_l попарно несовместных событий, где каждое V_k состоит из тех элементов П„, для которых все предыдущие сравне­ния образуют некоторую фиксированную последовательность срав­нений элементов с вполне определенными для данного к индекса­ми, и при этом возникающие значения Д1 совпадают с известными

из условия. В силу доказанного выше E(A L | V _fc) ^ -1 + ₂- для каж­
дого к ^ Z. Отсюда по формуле полного математического ожидания
E(A L | V)^ ¹

2п

-1 +

В сумме 2 ^пк, о которой идет речь в теореме 17.1, мы можем поло-fc=1 жить h_k = 1 для всех значений к, кроме какого-то одного значения к₀,

§ 17. Нижняя граница сложности в среднем 125

для которого h_ko = 1 - Т7-. Это дает нам

Е^ТгЛ =Е(т-1) + 1--^,

Дата добавления: 2014-01-11