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

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

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

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

е. конкретного массива длины n.) Тогда в соответствии с принципом Яо сложность этой рандомизированной сортировки не может быть меньшечем log2 n!, так как при равномерном распределении вероятностейЗадачина Πn для сложности в среднем детерминированных алгоритмов сортировки мы имеем в силу предложения . нижнюю границу log2 n!при любом n. Задачи. Для обсуждавшихся в задаче  алгоритмов сортировки вагонов функция 3n − 1 является нижней границей их сложности, откудаследует, что тот алгоритм, который требуется указать в задаче , является оптимальным в рассматриваемом классе.. Для сложности класса обсуждавшихся в задаче  алгоритмовпоиска двери в стене функция n является асимптотической нижнейграницей, откуда следует, что тот алгоритм, который требуется указать в задаче , является оптимальным по порядку сложности в рассматриваемом классе..

(Продолжение предыдущей задачи.) Для поиска двери можно указать класс A алгоритмов, каждый из которых определяетсянекоторым целым k ¾ 2: путник делает k шагов вправо, и если дверьне найдена, то возвращается назад и делает k шагов влево, и опятьвозвращается назад, если дверь не найдена; затем делает k 2 шаговвправо, возвращаясь назад в случае неуспеха, затем k 2 шагов влево и т. д. Таким образом, A = {A2 , A3 , ...}, и для сложности по числушагов имеем TAk (n) = 3n, если k = n, и TAk (n) > 3n, если k 6= n.

Какследствие, в классе A нет оптимального алгоритма, но каждый алгоритм из этого класса является оптимальным в нем по порядку сложности.Указание. Пусть m таково, что km−1 < n ¶ km . Возможно, что потребуетсячисло шагов, равное 2(k + k2 + ... + km ) + 2(k + k2 + ... + km−1 ) + n.. Нарисовать дерево быстрой сортировки для случая n = 3, считая, что первый элемент всегда выбирается в качестве разбивающего.. Дать другое доказательство предложения .. Рассмотретьпоследовательности из нулей и единиц, соответствующие результатам всех проводимых сравнений в процессе применения сортировкик массивам длины n (каждому массиву сопоставляется своя последовательность).Указание. Если некоторый алгоритм сортировки требует не более h(n)сравнений, то длина каждой из последовательностей не превосходит h(n),и общее число последовательностей не превосходит 2h(n) .Дополнительные примеры применения принципа Яо можно найти в [, гл.

]. Глава . Нижняя граница сложности. Оптимальные алгоритмы. Аналогично предыдущей задаче, дать другое доказательствопредложения ... Как уже отмечалось (со ссылкой на приложение D), n являетсянижней границей сложности как по числу аддитивных операций, таки по числу умножений для класса алгоритмов, вычисляющих значение полинома an x n + ... + a1 x + a0 с помощью операций сложения, вычитания и умножения (при рассмотрении числа n как размера входаx, a0 , a1 , ..., an ). Означает ли это, что при вычислении любого фиксированного полинома p(x) степени n при заданном значении переменной x потребуется не менее n аддитивных операций и n умножений?Указать такие нижние границы сложности (по числу аддитивных операций и по числу операций умножения) алгоритмов вычисления поn Pnлиномаx k , которые растут при n → ∞ существенно медленнее,k =0kчем n..

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

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