С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 24

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

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

С одной стороны, как мы знали и раньше, этасортировка очень удобна и имеет низкую пространственную сложность, с другой — мы видим теперь, что и в смысле временной сложности в среднем эта сортировка в определенном смысле может бытьотнесена к наилучшим.Можно показать существование оптимальной в среднем сортировки: для каждого фиксированного 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. Получаем21E∆ L = −2 − ǫ = −1 + 2ǫ > −1.2Тип AB.

Аналогично предыдущему можно показать, что при любом способе выбора индексов таких, что xi ∈ A, x j ∈ B, вероятность1выполнения неравенства xi > x j есть − ǫ , ǫ > 0. Получаем23 11 1E∆ L = −−ǫ −+ ǫ = −1 + ǫ > −1.2 22 2Тип AC. Рассматривается аналогично типу AB.В дальнейшем будет полезна оценка ǫ для сравнений типов ABи AC. Рассмотрим для определенности AB. Очевидно, что чем большесравнений к рассматриваемому моменту прошел элемент x j ∈ B, темменьше вероятность того, что элемент xi ∈ A окажется больше него. Глава .

Нижняя граница сложности. Оптимальные алгоритмыНаибольшая же вероятность получится в случае, когда x j сравнивался только с одним элементом, например с x s , и x s — это наименьшийэлемент исходного массива. Вычислим вероятность, с которой в этомслучае xi > x j . Итак, если упорядочить все элементы, кроме xi , x j , тоx s окажется наименьшим (первым). Общее число способов, которымик этой упорядоченной совокупности можно добавить xi , x j , с учетомx s < x j равно n(n − 2) (для добавления x j существует n − 2 способа, за nтем добавляем xi , и для этого существует n способов). Из них−12соответствуют неравенству xi < x j (возможен любой выбор двух средиn мест, кроме двух первых).

Интересующая нас вероятность равнаn(n − 2) −n+12n(n − 2)Это дает нам ǫ ¾=11− .22n1, и, таким образом,2nE∆ L ¾ −1 +12nдля AB и AC. Если при четном n удастся обойтись сравнениями ти3пов AA, BB, CC, то сравнений потребуется в точности n − 2. Если2n нечетно, то для решения задачи обязательно потребуется произвести хотя бы одно сравнение типа AB, AC или AD. Сравнение типа AD11дает ∆ L = − > −1 + .22nМожно убедиться и в том, что для сравнений типов AB и AC1выполняется E∆ L ¾ −1 + , если E∆ L рассматривается как матема2nтическое ожидание при условии, что значения ∆ L для всех предыдущих сравнений, предписываемых алгоритмом, известны.

Эти известные значения определяют некоторое событие V в вероятностном пространстве Πn . Событие V может быть представлено как сумма V1 + V2 + ... + Vl попарно несовместных событий, где каждое Vkсостоит из тех элементов Πn , для которых все предыдущие сравнения образуют некоторую фиксированную последовательность сравнений элементов с вполне определенными для данного k индексами, и при этом возникающие значения ∆ L совпадают с известными1для кажиз условия. В силу доказанного выше E(∆ L|Vk ) ¾ −1 +2nдого k ¶ l. Отсюда по формуле полного математического ожидания1E(∆ L|V) ¾ −1 + .2nτPВ суммеhk , о которой идет речь в теореме ., мы можем полоk =1жить hk = 1 для всех значений k, кроме какого-то одного значения k0 ,§ .

Нижняя граница сложности в среднемдля которого hk0 = 1 −E1. Это дает нам2nXτk =1‹1hk = E(τ − 1) + 1 − ,2nи с помощью следующего из теоремы . соотношенияXτ‹3Ehk ¾ n − 22k =1мы находимE(τ − 1) + 1 −13¾ n − 2.2n2После упрощения получаем32Eτ ¾ n − 2 +1.2nТаким образом, все доказано и для четных, и для нечетных n.Если существует алгоритм решения рассматриваемой задачи, который требует ровно (.) сравнений, то, по только что доказанному предложению, этот алгоритм является оптимальным в среднем почислу сравнений.

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

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