Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 25

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 25)

В любом двоичном дереве с m листьями сумма высотвсех листьев не меньше m log2 m.Доказательство. Пусть непусто множество M всех двоичных деревьев, для которых сумма высот всех листьев меньше m log2 m. Выберем в M какое-нибудь из деревьев, имеющих наименьшую сумму высот, и обозначим его U (сумму высот всех листьев будем обозначатьчерез H(U)). Это дерево не может состоять из одного лишь корня,потому что для такого дерева обсуждаемое неравенство выполнено.Далее, из корня этого дерева не может выходить только одно ребро,потому что для дерева, получающегося из исходного удалением корня и этого ребра, обсуждаемое неравенство не выполняется, и такоеновое дерево имеет сумму высот меньшую, чем дерево U (противоречие со способом выбора дерева U).

Поэтому из корня дерева Uвыходит два ребра, концы которых являются корнями двух деревьевU1 и U2 , для которых выполнено обсуждаемое неравенство. Пусть этидеревья имеют, соответственно, m1 и m2 листьев, m1 , m2 > 0. Имеемсоотношение для сумм высот всех листьевH(U) = H(U1 ) + H(U2 ) + m ¾ m1 log2 m1 + m2 log2 m2 + m.Отсюда получаемH(U) ¾ m1 log2 m1 + (m − m1 ) log2 (m − m1 ) + mпри некотором m1 таком, что 1 ¶ m1 ¶ m − 1.Легко показать, что при фиксированном m функция f (x) = x log2 x ++ (m − x) log2 (m − x) достигает минимума на отрезке [1, m − 1] в точке(не обязательно целой) m/2. ПоэтомуH(U) ¾mmmmlog2 + log2 + m = m log2 m.2222Но это противоречит способу выбора U.

Лемма доказана.Доказательство предложения .. Рассмотрим какое-либо деревосортировки массива длины n. Это дерево имеет ровно n! листьев,каждый лист соответствует перестановке элементов исходного массива. Появление на выходе рассматриваемой сортировки любой из этих1перестановок имеет одну и ту же вероятность , количество сравнеn!ний, приводящее к этой перестановке — это высота соответствующегоэтой перестановке листа. Поэтому математическое ожидание числа1сравнений равно произведению суммы высот всех листьев на .n! Глава . Нижняя граница сложности. Оптимальные алгоритмыСогласно лемме . сумма высот всех листьев должна быть неменьше, чем n! log2 n!.

Отсюда математическое ожидание числа сравнений не меньше, чем log2 n!.Доказанные ранее теорема . и предложение . справедливыв равной мере и для сложности в худшем случае, и для сложностив среднем. Принимая это во внимание, мы получаем следствие предложения .:Сортировка бинарными вставками и сортировка фон Неймана,а также быстрая сортировка являются оптимальными по порядкусложности в среднем по числу сравнений.К этому списку позднее мы добавим и рекурсивную сортировку слияниями. Наиболее же существенно упоминание в этом спискебыстрой сортировки. С одной стороны, как мы знали и раньше, этасортировка очень удобна и имеет низкую пространственную сложность, с другой — мы видим теперь, что и в смысле временной сложности в среднем эта сортировка в определенном смысле может бытьотнесена к наилучшим.Можно показать существование оптимальной в среднем сортировки: для каждого фиксированного n в множестве всех деревьев сортировки массивов длины n можно рассмотреть подмножество деревьев,имеющих наименьшую сумму H высот всех листьев (тогда и H /n!будет иметь наименьшее значение), и взять какое-нибудь из деревьев этого подмножества.

Определяя сортировку этим способом длявсех n мы получаем оптимальную сортировку. Для любой оптимальной в среднем сортировки выполнено¯T¯opt (n) ∼ log2 n! ∼ n log2 n,так как, например, мы имеем TvN (n) ∼ log2 n! иTvN (n) ¾ ¯T¯vN (n) ¾ ¯T¯opt (n) ¾ log2 n!.В этом примере, как и во всем этом параграфе, мы не касаемсярандомизированных алгоритмов, о которых будет говориться в § .Как мы ранее наблюдали в некоторых примерах, рассмотрениефункции L, подобранной надлежащим образом, и изучение изменения ее значений в ходе выполнения алгоритма нередко позволяетполучать хорошие оценки (в частности, нижние границы) сложностив худшем случае.

Рассмотрение такого рода функций может приводить к цели и при исследовании сложности в среднем. В задаче функцию L можно определить как максимум значений компонент§ . Нижняя граница сложности в среднеминверсионного вектора перестановки. Эта функция является случайной величиной на Πn , при этом ∆ L = −1 на каждом шаге алгоритма.В других ситуациях начальное значение L может определяться однозначно, тогда как ∆ L является случайной величиной.

Сформулируемтеорему, полезную в этих ситуациях.Теорема .. Пусть ξ1 , ξ2 , ... — последовательность неотрицательных случайных величин на некотором вероятностном пространстве. Пусть числовая последовательность h1 , h2 , ... такова, что длякаждого k ¾ 1 выполнено E(ξk |ξ1 , ξ2 , ..., ξk−1 ) ¶ hk при всех значенияхξ1 , ξ2 , ..., ξk−1 . Зафиксируем неотрицательное число q и введем целочисленную случайную величину§nªXτ = min n:ξk ¾ q .k =1Пусть τ < ∞ всюду на рассматриваемом вероятностном пространP‹τстве.

Тогда Ehk ¾ q.k =1Доказательство приведено в приложении E.Для того чтобы воспользоваться этой теоремой, можно опять попытаться определить некоторую неотрицательную функцию L, отражающую степень «недорешенности» рассматриваемой задачи: значение L равно нулю, если алгоритм доработал до конца и задача решена. Считаем, что всем входам фиксированного размера сопоставляется одно и то же значение функции L.

После выбора такой функции L мы должны показать, что последовательность величин E(−∆ L),соответствующих идущим друг за другом этапам алгоритма, ограничена сверху некоторой известной числовой последовательностьюh1 , h2 , ...; тогда случайная величина τ, равная для данного входа общему количеству этапов, приводящих к завершению алгоритма, таP‹τкова, что Ehk ¾ q, где q — значение функции L, сопоставляеk =1мое входам алгоритма рассматриваемого фиксированного размера.Это неравенство можно использовать, чтобы оценить снизу значениеEτ. Конечность величины τ следует из завершимости алгоритма длялюбого входа.Пример .. Вернемся к задаче одновременного выбора наибольшего и наименьшего элементов массива длины n, n ¾ 2, с помощьюсравнений (пример .).

Вероятностным пространством здесь вновьбудем считать Πn . Каждая перестановка из Πn отражает, как обычно, Глава . Нижняя граница сложности. Оптимальные алгоритмывзаимный порядок элементов исходного массива. Все перестановкисчитаются равновероятными.Чтобы воспользоваться теоремой ., мы полагаем, что случайные величины ξ1 , ξ2 , ... для произвольного алгоритма одновременного выбора наибольшего и наименьшего элементов равны значениям−∆ L на последовательных шагах этого алгоритма, об определениифункции L будет сказано ниже.

Значения ξ1 , ξ2 , ... зависят от конкретной перестановки из Πn , отражающей взаимный порядок элементов в исходном массиве. После того, как алгоритм закончил работу,значения ξk при последующих значениях k равны нулю.Предложение .. Функция32f (n) =31n−2+ ,22n n − 2,если n четно,(.)если n нечетно,является нижней границей сложности в среднем алгоритмов одновременного выбора наибольшего и наименьшего элементов массива длины n, n ¾ 2, c помощью сравнений.Доказательство.

Вновь обратимся к множествам A, B, C, D, к рассмотренным в доказательстве предложения . типам AA, AB, ..., DDсравнений, количествам a, b, c, d элементов множеств A, B, C, D и функ3ции L(a, b, c, d) = a + b + c − 2 (равенство L = 0 является необходимым2и достаточным условием того, что искомые элементы найдены).Пусть в процессе выбора наибольшего и наименьшего элементовмассива уже произведены некоторые сравнения элементов этого массива. При каждом из этих сравнений получался некоторый результат«истина» или «ложь», и эти результаты нам известны.

Если процессвыбора наибольшего и наименьшего элементов еще не завершен, тоследующим шагом вновь будет некоторое сравнение одного из типовAA, AB, ..., DD. Сравнения AB, AC и BC представляют особый интерес,так как можно бы предположить, что здесь получится E∆ L < −1. Нона самом деле это неравенство не имеет места ни при одном из этихтрех типов сравнений.Тип BC. Покажем невозможность такого выбора индексов i и j,основанного только на результатах уже произведенных сравнений,что xi ∈ B, x j ∈ C и при этом с вероятностью, не меньшей половины,выполняется xi < x j .Пусть сделан некий выбор индексов i и j, при котором xi ∈ B,x j ∈ C. Рассмотрим множество M всех массивов y1 , y2 , ..., yn , которые§ . Нижняя граница сложности в среднемполучаются перестановками элементов массива x1 , x2 , ..., xn и приэтом сравнения элементов с теми же самыми индексами, которыеиспользовались в уже произведенных сравнениях элементов массиваx1 , x2 , ..., xn , дают для массивов из M результаты, совпадающие с полученными для x1 , x2 , ..., xn .

Представим множество M в виде объединения двух непересекающихся подмножеств M1 и M2 , где в M1 входят те массивы, для которых yi < y j , а в M2 — те, для которых y j < yi .Покажем, что в M1 больше элементов, чем в M2 . Операция обменаyi ↔ y j определяет взаимно однозначное отображение на себя множества всех массивов, которые получаются перестановками элементов массива x1 , x2 , ..., xn . Обратным к этому отображению являетсяоно само.

В силу определения множеств B и C это отображение переводит элементы множества M1 в элементы множества M2 . Следовательно, в M1 элементов не больше, чем в M2 . Но в M2 найдется массив, который при этом отображении не переходит в массив из M1 и,более того, вообще покидает множество M (чтобы убедиться в этом,достаточно заметить, что в M2 имеется такой массив y1 , y2 , ..., yn , длякоторого y j = min{ y1 , y2 , ..., yn }). Поэтому в M1 элементов меньше,чем в M2 . Если m1 , m2 обозначают количества элементов множествM1 и M2 , то имеемm2m1<m1 + m2и, следовательно,m1 + m2m11< .m1 + m22Таким образом, вероятность того, что i-й элемент меньше j-го, есть1− ǫ , ǫ > 0.

Характеристики

Список файлов лекций