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

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

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

Получаем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.Если существует алгоритм решения рассматриваемой задачи, который требует ровно (.) сравнений, то, по только что доказанному предложению, этот алгоритм является оптимальным в среднем почислу сравнений.

Укажем такой алгоритм. Если n четно, то действуемв соответствии с алгоритмом, обсуждавшимся в примере .. Пустьn = 2k + 1, k ¾ 0. Находимmi = min{x2i−1 , x2i },Mi = max{x2i−1 , x2i },i = 1, 2, ..., k, иm = min{m1 , m2 , ..., mk },что потребует n − 2 сравнений. Без дополнительных затрат можнонайти s, 1 ¶ s ¶ 2k, такое, что m = m s . Далее сравниваем xn (т. е. x2k+1 )c M s . Согласно рассуждениям, проведенным выше при анализе срав11нений типа AB, вероятность того, что xn > M s , равна − . Если22nxn > M s , то результатом работы алгоритма будетmax{M1 , ..., M s−1, M s+1 , ..., Mk , xn },m,в противном случае —max{M1 , M2 , ..., Mk },min{m, xn }.Среднее число сравнений при нечетном n равно 11311n−11−+2++−1 = n−2+ ,(n − 2) +2что и требовалось.2n22n222n Глава . Нижняя граница сложности.

Оптимальные алгоритмыСуществует оптимальный в среднем алгоритм одновременного нахождения наибольшего и наименьшего элементов массива длины n,n ¾ 2, с помощью сравнений. Этот алгоритм имеет сложность (.).§ . Нижние границы сложности рандомизированныхалгоритмов. Принцип ЯоЭтот параграф начнем с формулировки и обсуждения одного факта изтеории игр. С произвольной квадратной числовой матрицей M = (mij )порядка k связывается матричная игра двух игроков, которых мы назовем I и J. Один раунд игры состоит в том, что I и J независимодруг от друга называют соответственно целые i и j из диапазона от 1до k, и после этого J выплачивает своему сопернику I сумму в mijрублей (при mij < 0 сумма в −mij рублей выплачивается игроком Iигроку J).

Стратегией называется вектор p = (p1 , p2 , ..., pk ) с вещественными неотрицательными компонентами, в сумме дающими единицу; стратегии (1, 0, ..., 0), (0, 1, ..., 0), ..., (0, 0, ..., 1) называются чистыми. Допустим, что игроки независимо избирают для себя некоторые стратегии — обозначим их соответственно p и q, — и затем в последовательных раундах игрок I называет число i с вероятностью pi ,а игрок J называет число j с вероятностью q j . Математическое ожидание выигрыша игрока I равно, как нетрудно подсчитать,XXmij pi q j ,ijэту величину мы будем обозначать M(p, q). Допустим также, что вместо проведения большого числа раундов игры каждый из игроков,основываясь на известной матрице M, один раз выбирает, независимо от другого игрока, для себя некоторую стратегию и сообщаетее судье, который по полученным от игроков стратегиям (векторамp и q) вычисляет M(p, q), умножает его на количество предполагавшихся раундов и объявляет полученное число выигрышем игрока I.Естественно, что игрок I заинтересован в нахождении такой стратегии, которая максимизирует M(p, q), а у игрока J цели прямо противоположные.

Одна из теорем раздела теории игр, посвященногоматричным играм  , утверждает, что для игроков существуют оптимальные стратегии p ∗ , q ∗ такие, что M(p ∗ , q ∗ ) является одновременнозначением величинmax min M(p, q) иpqСм., например, [, теорема .].min max M(p, q).qp§ . Нижние границы сложности рандомизированных алгоритмов В дальнейшем нас не будут интересовать оптимальные стратегии, однако равенствоmax min M(p, q) = min max M(p, q)qpqp(.)окажется для нас очень ценным.При фиксированной стратегии p значение min M(p, q) равно миqнимальному значению средиXXXmi1 pi ,mi2 pi , ...,mik pi ,iт.

е. minjPiimij pi (в качестве стратегии q, на которой достигается ми-iнимум, выступает некотораячистая стратегия). Аналогичным обPразом max M(p, q) = max mij q j . Это позволяет переписать равенpiство (.) в видеmax minpjjXimij pi = min maxqiXmij q j ,(.)jоткуда следует, что для любых стратегий p = (p1 , p2 , ..., pk ) и q = (q1 ,q2 , ..., qk ) выполненоXXminmij pi ¶ maxmij q j .(.)jiijТо, что исходная матрица квадратная, не играло никакой роли в выводе последней формулы, каждая из переменных i и j могла пробегать свое множество значений.

Можно даже не нумеровать строкии столбцы исходной матрицы, а дать им какие-то имена. Для матриц с такого рода именованием строк и столбцов чаще используютназвание таблица.Вернемся теперь от матричных игр к анализу сложности алгоритмов. Пусть имеется конечное множество A алгоритмов решениянекоторой задачи и конечное множество X входов фиксированногоразмера, и для них составлена числовая таблица, элементы которойпроиндексированы элементами множества X (первый индекс) и множества A (второй индекс).

В качестве элемента таблицы с индексами x, A берется величина затрат (например, временных) C A (x). Еслирассмотреть какие-либо распределения вероятностей на X и A , тов силу (.) будем иметьmin E X C A (x) ¶ max EA C A (x),A∈Ax∈ X(.) Глава . Нижняя граница сложности. Оптимальные алгоритмыгде символами E X и EA обозначены математические ожидания, связанные с заданными (произвольными) распределениями вероятностей на X и A .Будем рассматривать рандомизированный алгоритм как конечноемножество детерминированных («обычных») алгоритмов с некоторым распределением вероятностей на нем, — о возможности такоговзгляда на рандомизированные алгоритмы говорилось в конце § .Тогда можно определить усредненные затраты этого рандомизированного алгоритма для каждого входа.

Фиксируя размер входа, мыможем рассмотреть сложность в худшем случае такого рандомизированного алгоритма A как максимум усредненных затрат по входам данного размера, эта сложность записана в правой части неравенства (.). Левая же часть этого неравенства может быть интерпретирована как наименьшая из сложностей в среднем алгоритмовкласса A , для определения этой сложности используется некотороераспределение вероятностей на X .Мы приходим к принципу, предложенному А. Яо.Теорема . (принцип Яо). Пусть для размера входа зафиксировано некоторое значение n, и пусть все входы размера n образуютконечное множество X , на котором задано некоторое распределениевероятностей. Пусть A — конечное множество алгоритмов, применимых к элементам множества X , и пусть на A тоже задано некоторое распределение вероятностей.

Множество A с этим распределением можно рассматривать как единый рандомизированный алгоритм, считая его сложностью T(n) усредненные затраты в худшемслучае. Тогда, если найти некоторую нижнюю границу f (n) сложностей в среднем (в соответствии с данным распределением вероятностей на множестве X входов размера n) всех детерминированныхалгоритмов класса A , то, независимо от конкретного вида распределений на X и A , будет выполняться неравенство f (n) ¶ T(n).Пример .. Рассмотрим произвольную рандомизированную сортировку массивов фиксированной длины n, которую, по крайней мере теоретически, можно задать как конечное множество детерминированных алгоритмов сортировки массивов длины n с приписанными этим детерминированным алгоритмам вероятностями, в суммедающими единицу. (Предполагаем, что это вероятностное пространство алгоритмов не зависит от конкретного входа, т. е.

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

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