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

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

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

е. алгоритм 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 с помощью сравнений.§ .

Нижняя граница сложности в среднемПрежде всего докажем вспомогательное утверждение.Лемма .. В любом двоичном дереве с 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!.Доказанные ранее теорема . и предложение . справедливыв равной мере и для сложности в худшем случае, и для сложностив среднем.

Принимая это во внимание, мы получаем следствие предложения .:Сортировка бинарными вставками и сортировка фон Неймана,а также быстрая сортировка являются оптимальными по порядкусложности в среднем по числу сравнений.К этому списку позднее мы добавим и рекурсивную сортировку слияниями. Наиболее же существенно упоминание в этом спискебыстрой сортировки.

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

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