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

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

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

Пусть A, B ∈ A оптимальны по порядку сложностив A . Тогда TA (n) = Θ(TB (n)).Доказательство. Так как алгоритм A оптимален по порядку сложности, имеем TB (n) = Ω(TA (n)) или, что то же самое, TA (n) = O(TB (n)),что вместе с TA (n) = Ω(TB (n)) (алгоритм B оптимален по порядкусложности) дает TA (n) = Θ(TB (n)).§ . Асимптотические нижние границыУкажем достаточное условие оптимальности алгоритма по порядку сложности.Теорема .. Если функция f (n) является асимптотической нижней границей сложности принадлежащих классу A алгоритмов и еслиалгоритм A ∈ A таков, что TA (n) = O( f (n)), то этот алгоритм оптимален в A по порядку сложности и TA (n) = Θ( f (n)).Доказательство. Для произвольного B ∈ A имеем TB (n) = Ω( f (n));учитывая, что TA (n) = O( f (n)), получаем TB (n) = Ω(TA (n)), т.

е. алгоритм A оптимален по порядку сложности.Из TA (n) = Ω( f (n)) и TA (n) = O( f (n)) получаем TA (n) = Θ( f (n)).Пример .. Из предложения . следует, что функция f (n) == log2 n является асимптотической нижней границей сложности алгоритмов вычисления an с помощью умножений (эта функция дажеявляется нижней границей в смысле определения .). Для сложности бинарного алгоритма вычисления an мы имеем TRS (n) = O(log n)(см. пример .). Из теоремы . теперь получаем:Бинарный алгоритм возведения в степень является оптимальнымпо порядку сложности в классе алгоритмов вычисления an с помощьюумножений.Иногда, хотя не часто, из совершенно элементарных соображенийудается найти такую нижнюю границу сложности, что далее по теореме . оказывается возможным обосновать оптимальность некоторого известного алгоритма по порядку сложности. Рассмотрим двапримера из теории графов.Пример ..

Вопрос о существовании и построении эйлеровацикла данного ориентированного графа сформулирован в задаче .Остановимся на случае связного графа. Очевидно, что если избратьчисло ребер | E | в качестве размера входа, то | E | является нижнейграницей сложности класса всех алгоритмов построения эйлеровыхциклов, так как, во-первых, любой эйлеров цикл содержит по определению все ребра графа и на любое ребро уйдет по крайней мереодна операция, и, во-вторых, для любого натурального n существуетграф с | E | = n, содержащий эйлеров цикл. Поэтому тот алгоритм сосложностью O(| E |), который требуется дать в задаче , будет оптимальным по порядку сложности.Пример .. Рассмотрим задачу построения минимального остовного (покрывающего) дерева данного связного графа, каждое ребро Глава .

Нижняя граница сложности. Оптимальные алгоритмыкоторого имеет некоторый неотрицательный вес. Имеется в виду дерево:(a) которое охватывает все вершины данного графа,(b) все ребра которого являются ребрами данного графа,(c) которое среди всех деревьев, обладающих свойствами (a), (b),имеет минимальный суммарный вес ребер  .Будем считать, что граф не содержит кратных ребер. Пример графа с соответствующим остовным деревом дан на рис. .

Для построения минимального остовного дерева известны остроумные алгоритмы, например,45алгоритм Р. Прима  с оценкой сложности202O(| E | + | V | log| V |).1(.)В этой оценке | V | и | E | рассматриваютсякак два параметра размера входа. Не обсуждая вопрос, является или нет алгоритм2Прима оптимальным по порядку сложности при таком выборе параметров размераРис. . Граф с припивхода и не рассматривая детали алгоритмасанными ребрам весамиПрима, мы покажем, что этот алгоритм опи его остовное дерево.тимален по порядку сложности при использовании | V | как размера (единственного параметра размера) входа. Так как среди всех графов без кратных ребер, имеющих | V | вершин, наибольшее число ребер3636| V |(| V | − 1)2имеет полный граф, то оценка (.) имеет следствием оценкуO(| V |2 ).

С другой стороны, асимптотическая нижняя граница Ω(| V |2 )для алгоритмов такого рода получается тривиально: эту оценку допускает число ребер полного графа, а на каждое ребро графа алгоритм затрачивает по крайней мере одну операцию (он не может непринять в расчет вес какого-либо ребра).Если использовать для входов алгоритмов построения остовногодерева размер | V |, то | V |2 даст асимптотическую нижнюю границусложности этих алгоритмов, и алгоритм Прима будет оптимальным по порядку сложности (его сложность, соответствующая этомуразмеру входа, есть Θ(| V |2 )).См. [, гл.

].Этот алгоритм описан, например, в [, разд. .].§ . Асимптотические нижние границыИз этого примера видно, что само свойство оптимальности находится в зависимости от выбора размера входа  .В следующем примере, касающемся сортировки массивов, рассматривается сложность в худшем случае по числу сравнений.Пример .. Аналогично тому, как это сделано в примере .,мы получаем, что любая сортировка, сложность которой допускаетоценку O(log n!), является оптимальной по порядку сложности. В силуформулы Стирлинга мы имеем n log2 n = O(log n!), откуда следует, чтолюбая сортировка, сложность которой по числу сравнений допускаетоценку O(n log n), является оптимальной по порядку сложности.Сортировка бинарными вставками и сортировка фон Неймана являются оптимальными по порядку сложности по числу сравнений.(Позднее мы установим оценку O(n log n) и для сложности рекурсивной сортировки слияниями.) Эти сортировки имеют разные сложности как функции от n: например, TvN (5) = 9, TB (5) = 8.

Но, повторим,их сложности являются величинами одного порядка при n → ∞.Резюмируем наши наблюдения.Предложение .. Необходимым и достаточным условием оптимальности сортировки по порядку сложности является справедливость оценки O(n log n) для сложности этой сортировки. Если длянекоторой сортировки справедлива оценка O(n log n), то справедливаи оценка Θ(n log n).Доказательство.

Достаточность уже установлена выше. Оставшаяся часть доказательства следует, например, из теоремы . и оптимальности по порядку сложности сортировки бинарными вставками.Заметим при этом, что для сортировок бинарными вставками ифон Неймана справедливо значительно более сильное утверждение,чем утверждение об их оптимальности по порядку сложности. Дляих сложностей и сложности Topt (n) оптимального алгоритма имеетместо асимптотическая эквивалентность:TB (n) ∼ TvN (n) ∼ Topt (n) ∼ n log2 n ∼ log2 n!.Коснемся нижних границ пространственной сложности алгоритмовсортировки. Если из всех этих алгоритмов выделить класс таких, которые используют для перемещения элементов обмены (↔), а не присваЭтот пример сообщил автору Е. В. Зима. Глава .

Нижняя граница сложности. Оптимальные алгоритмыивания (:=), то для этого класса единственной нижней границей, еслиговорить о функциях, принимающих неотрицательные значения, будеттождественно равная нулю функция, так как существуют, например,пузырьковая сортировка, сортировки простыми и бинарными вставками, не использующие дополнительных переменных того типа, к которому относятся элементы сортируемого массива. (То, что требуютсяпеременные для хранения значений индексов элементов, несущественно при изучении алгебраической сложности сортировки.) Алгоритмы,использующие присваивания для перемещения сортируемых элементов, не могут, естественно, обойтись без дополнительного места дляхранения хотя бы одной величины того же типа, что и элементы сортируемого массива, и одной из нижних границ будет функция, тождественно равная единице.

Если рассматривать все алгоритмы сортировки вместе, то вновь единственная неотрицательная целочисленная граница — это 0. В соответствии с этим определяются как оптимальные,так и оптимальные по порядку сложности алгоритмы.Для произвольного класса A оптимальный по порядку сложностиалгоритм может и не существовать: если A содержит всего два алгоритма A1 , A2 и при этом A1 имеет низкую сложность при четныхзначениях целочисленного размера входа n и высокую — при нечетных, а A2 — наоборот, то, очевидно, ни A1 , ни A2 не будут оптимальными в A по порядку сложности (представим себе, что TA1 == (1 + (−1)n )n, TA2 = (1 − (−1)n )n).

В то же время, если допустить, чтоTA1 = (2 + (−1)n )n, TA2 = (2 − (−1)n )n, то TA1 (n) = Θ(TA2 (n)) (обе функции имеют порядок n), и это говорит о возможности существованияоптимального по порядку сложности алгоритма при отсутствии оптимального.§ . Нижняя граница сложности в среднемПри рассмотрении сложности в среднем мы основываемся на тех жепонятиях нижней границы, оптимального и оптимального по порядкусложности алгоритма, которые были введены для сложности в худшем случае.Пример ..

Вновь обратимся к классу алгоритмов сортировки.Будем, как и в § , рассматривать вероятностное пространство Πn .Предложение .. Функция log2 n! является нижней границейсложности в среднем для класса алгоритмов сортировки массивовдлины n с помощью сравнений.§ . Нижняя граница сложности в среднемПрежде всего докажем вспомогательное утверждение.Лемма ..

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

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