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

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

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

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

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

119

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

Лемма 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!~nlog₂n,

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

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

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

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