С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 5
Текст из файла (страница 5)
число листьев 2 hдостигается на полном двоичном дереве, т.е. дереве, у которого заполнены все уровни).Очевидно, что h в данном случае соответствует сложности алгоритма. В дереве сортировкиn! листьев, откуда получаем нижнюю границу сложности для алгоритмов сортировки:2T ( n ) ≥ n! ⇒ T (n) ≥ ⎡log 2 n!⎤ .Вспомним алгоритм бинарного поиска: есть массив x1 < x2 < ... < xn и некоторое заданноечисло y, для которого требуется найти место в массиве, чтобы сохранилась упорядоченность.Для вставки y существует (n + 1) возможность: y ≤ x1 ; x1 < y ≤ x2 ; …; xn < y . Задачаалгоритма заключается в определении номера возможности.
Опять же можно строить дерево,24но в данном случае листьев на дереве будет (n + 1) листьев, и оценка для сложности приметвид: T (n) ≥ ⎡log 2 (n + 1)⎤ .Вспомним алгоритм вычисления степени a n с помощью умножений. Каждый этапалгоритма может быть охарактеризован тем, какие степени мы имеем на текущий момент:a i1 ,..., a im и более того, какой максимальный порядок встречается в этом наборе. На каждомшаге максимальный порядок может увеличиться не более чем в 2 раза.
Определим на набореa i1 ,..., a im функциюλ = log 2 n − log 2 i123constгде i — максимум из i1 ,..., im . Тогда функция на каждом шаге может уменьшить своёзначение не более чем на 1. Очевидно, что в этих обозначениях алгоритм заканчивает работу,как только λ станет ≤ 0 . Отсюда получаем нижнюю границу сложности алгоритма: log 2 n .Определение. Если в A ∃A : TA (n) является нижней границей сложности для A , то Aявляется оптимальным в этом классе и ∀B ∈ A ⇒ TB (n) ≥ TA (n) .Найти оптимальный алгоритм значит найти нижнюю границу для алгоритмов данногокласса и предъявить алгоритм с такой сложностью.Рассмотрим задачу: имеется массив, требуется найти и минимальный, и максимальный⎡ 3n ⎤элемент.
Покажем, что нижняя граница сложности составляет f (n) = ⎢ ⎥ − 2 и приведём⎢2⎥оптимальный алгоритм.Каждый этап произвольного алгоритма V, решающего эту задачу, характеризуетсяследующей четвёркой множеств элементов массива: ( A, B, C , D) , где A — множествоэлементов, не участвовавших в сравнениях; B — множество элементов, которые во всехсравнениях оказывались большими; C — множество элементов, которые во всех сравненияхоказывались меньшими; D — множество элементов, которые в некоторых сравнениях былибольше, а в других — меньше. Начальная ситуация в ведённых обозначениях выглядит как(n, 0, 0, 0) , конечная — (0, 1, 1, n − 2) , т.е. множества B и C состоят из одного элемента,которые и будут максимальным и минимальным соответственно.3a + b + c − 2 , где a, b и c соответствуют числу элементов в2соответствующих множествах A, B и C.
Возможны следующие сравнения исоответствующие изменения функции λ :( A, B, C , D)изменение λсравнение(a − 2, b + 1, c + 1, d )AA−113(a − 1, b, c + 1, d ) | (a − 1, b, c, d + 1)− |−AB2213(a − 1, b + 1, c, d ) | (a − 1, b, c, d + 1)− |−AC2211(a − 1, b + 1, c, d ) | (a − 1, b, c + 1, d )− |−AD22(a, b − 1, c, d + 1)BB−1(a, b − 1, c − 1, d + 2) | (a, b, c, d )−2 | 0BC(a, b − 1, c, d + 1) | (a, b, c, d )−1 | 0BDРассмотрим функцию λ (a, b, c) =25(a, b, c − 1, d + 1)(a, b, c − 1, d + 1) | (a, b, c, d )(a, b, c, d )CCCDDD−1−1 | 00Здесь AA означает сравнение элемента из A с элементом из A; AB — сравнение элемента из Aс элементом из B и т.д.В худшем случае шаг от шага λ уменьшается не более, чем на 1, откуда получаем нижнюю⎡ 3n ⎤границу сложности f (n) = ⎢ ⎥ − 2 .⎢2⎥Приведём оптимальный алгоритм, решающий поставленную задачу: изначально имеетсямассив из n элементов x1 ,..., xn .
Разобьём исходный массив на пары x1 , x2 ; x3 , x4 ; … В каждойпаре найдём минимум и максимум за одно сравнение. Тогда минимальные элементы из паробразуют множество m1 , m2 ,... , а максимальные — M 1 , M 2 ,... Среди m1 , m2 ,... найдёмминимальный, среди M 1 , M 2 ,... — максимальный. Если на первом шаге был непарныйэлемент (n — нечётное), то на него потребуется ещё два сравнения с найденнымиминимумом и максимумом. В итоге на каждую пару тратится 3 сравнения.Надо добавить, что оптимальный алгоритм не обязан существовать. Например, врассматриваемом классе алгоритмов имеется всего 2 алгоритма, один из которых быстроработает для чётных n, второй — для нечётных.Оптимальные алгоритмы сортировки.Для построения оптимального алгоритма сортировки можно, конечно, построить всевозможные бинарные деревья с n! листьями, выбрать дерево с наименьшей высотой ипредъявить.Считалось, что алгоритм бинарными вставками является оптимальный.
Но для n = 5 емупонадобиться 8 сравнений, в то время как полученная выше нижняя граница даёт⎡log 2 n!⎤ = ⎡log 2 5!⎤ = 7 .⇒⇒⇒а)б)сравнений:233+25Очевидно, что для полного упорядочения потребуется ещё не более 2-х сравнений, в итогеполучим 7, т.е. алгоритм для сортировки массива длины 5, сложность которого равна 7,существует. Интересно, что уже для n = 12 оптимальный алгоритм потребует ⎡log 2 12!⎤ + 1сравнений.Бинарный алгоритм возведения в степень не является оптимальным. Оптимальным являетсяалгоритм, называемый схемой Горнера, который по заданным числам a0 , a1 , ..., an , xвычисляет значение выражения an x n + an−1 x n−1 + ... + a1 x + a0 и требует n умножений.Нужно отметить, что оптимальных алгоритмов человечество знает не много.
Поэтомупонятие оптимальности хорошо было бы расширить.Определение. Асимптотической нижней границей сложности алгоритмов некоторого классаA называется такая функция f (n) , что ∀A ∈ A ⇒ TA (n) = Ω( f (n) ) .26Определение. Алгоритм называется асимптотически оптимальным (оптимальным попорядку сложности), если TA (n) является асимптотической нижней границей сложности и∀B ∈ A ⇒ TB (n) = Ω(TA (n) ) .Оптимальных по порядку сложности алгоритмов в определённом класс может бытьнесколько, но оптимальная асимптотическая сложность определена однозначно.Пусть A и B — оптимальные алгоритмы по порядку сложности.
Тогда справедливоTB (n) = Ω(TA (n) ) , что эквивалентно тому, что TA (n) = O (TB (n) ) .Утверждение. TA (n) = Θ(TB (n) ) .Доказательство:TB (n) = Ω(TA (n) )⎫⎬ ⇒ TA (n) = Θ(TB (n) ) .TA (n) = Ω(TB (n) )⎭Утверждение. Если f (n) является асимптотической нижней границей сложностиалгоритмов класса A , A ∈ A и TA (n) = O ( f (n) ) , то A — оптимальный по порядкусложности и более того TA (n) = Θ( f (n) ) .Доказательство: f (n) — асимптотическая нижняя граница сложности ⇒ TA (n) = Ω( f (n) ) ,но TA (n) = O ( f (n) ) по условию ⇒ TA (n) = Θ( f (n) ) ⇒ A — оптимальный по порядкусложности.Алгоритм возведения в степень (RS), рассмотренный ранее, не является оптимальным, ноявляется асимптотически оптимальным, т.к.
ранее было показано, что TRS (n) = Ω(log n ) иTRS (n) < 2 log 2 n , а следовательно, он является асимптотически оптимальным.Если мы обнаруживаем, что для некоторого алгоритма сортировки его сложность можетбыть оценена через O(log n!) или, используя формулу Стирлинга, O(n log n) , то он являетсяоптимальным по порядку сложности. Поэтому сортировка фон Неймана и сортировкабинарными вставками являются оптимальными по порядку сложности. Позднее в этотсписок добавим ещё алгоритм сортировки слияниями. А равны ли TvN (n) и TB (n) ? Ответ: нет,это не одно и то же, т.к. хотя бы для n = 5 имеем TvN (n) = 9 , TB (n) = 8 .Для алгоритма построения Эйлерова цикла (частный случай вояжа) была получена оценкаO ( E ) , но очевидно, что меньше, чем за E шагов, его построить нельзя.
Поэтому алгоритмявляется оптимальным по порядку сложности.Рассмотрим взвешенный связный граф без кратных рёбер. Остовным деревом будемназывать подграф, который: 1) охватывает все вершины; 2) ребрами его являются рёбраисходного графа; 3) сумма весов ребер минимальна.Пример.54420231636⇒2132227Известен алгоритм Прима построения остовного дерева со сложностью O ( E + V log V ) . Ноесли в качестве размера входа рассматривать только V , то алгоритм будет оптимальным попорядку сложности.Среди всех графов имеющих V вершин наибольшее количество рёбер имеет полный граф:V (V − 1)2, следовательно, алгоритм Прима допускает оценку O V , но с другой22стороны существуют полные графы, и следовательно, Ω V .
Поэтому он оптимален иE =( )( ).допускает оценку Θ V( )2Следует отметить, что не всегда существует оптимальный алгоритм по порядку сложности.Например, в классе всего два алгоритма, один из которых быстро работает для чётных n , авторой — для нечётных. Но, тем не менее, сложности алгоритмов, оптимальных по порядкусложности, являются величинами одного порядка.Пока рассматривались оптимальные алгоритмы по порядку сложности, и сложность быласложностью в худшем случае. Можно также рассматривать по сложности в среднем.Утверждение. log 2 n! является нижней границей сложности в среднем для алгоритмовсортировки.Доказательству утверждения предпошлём лемму.Лемма. В любом двоичном дереве с m листьями сумма высот всех листьев ≥ m log 2 m .Доказательство леммы проведём от противного: пусть сделанное утверждение не верно.Тогда из всех деревьев, для которых это не так, возьмём дерево U с минимальной суммойвысот.
Это дерево не может состоять из одной вершины, т.к. 0 ≥ 1 ⋅ log 2 1 = 0 . Следовательно,из корня этого дерева исходит одно или два ребра. Пусть исходит одно ребро:U′Но этого быть не может, т.к. для U ′ утверждение должно быть не выполнено, иначедобавление ребра лишь увеличит сумму высот и получим, что для U утверждениевыполнено, но это не так. А если для U ′ утверждение не выполнено, тогда U не являетсядеревом с минимальной суммой высот (сумма высот у U ′ меньше, чем у U ). Поэтому изкорня может исходить только 2 ребра:U2U1Обозначим сумму высот всех листьев дерева через H (U ) , тогда H (U ) = H (U1 ) + H (U 2 ) + m ,т.к.
к каждой высоте деревьев U1 и U 2 прибавится единица, а сумма листьев в деревьях U1 иU 2 равно m (в дереве U m листьев). Обозначим через m1 , m2 количества листьев вдеревьях U1 и U 2 соответственно. Для деревьев U1 и U 2 утверждение должно бытьвыполнено, т.к. U — дерево с минимальной суммой высот, для которого утверждение невыполнено. Тогда H (U1 ) ≥ m1 log 2 m1 и H (U 2 ) ≥ m2 log 2 m2 .28H (U ) ≥ m1 log 2 m1 + m2 log 2 m2 + mС учётом m = m1 + m2 получаем:H (U ) ≥ m1 log 2 m1 + (m − m1 ) log 2 (m − m1 ) + m , 1 ≤ m1 ≤ m − 1Рассмотрим функцию f ( x) = x log 2 x + (m − x) log 2 (m − x) . Найдём минимум этой функции наотрезке [1, m − 1] . Проведя стандартный анализ с привлечением аппарата производных,m⇒получаем, что минимум достигается в точке x =2H (U ) ≥mm mmlog 2 + log 2 + m = m log 2 m ,22 22что противоречит сделанному предположению.
Лемма доказана.Доказательство утверждения: рассматривается пространство перестановок Π n . Деревосортировки имеет n! листьев, и нам нужно посчитать математическое ожидание суммарныхзатрат. Суммарные затраты совпадают с суммой высот всех листьев и, согласно лемме, они≥ n!log 2 n! . Чтобы посчитать математическое ожидание, достаточно суммарные затраты1, откуда получаем нижнюю границу сложности в среднем:умножить наn!1⋅ n!log 2 n!= log 2 n! .n!Согласно этому утверждению, сортировка фон Неймана и сортировка бинарными вставкамибудут оптимальными по порядку сложности в среднем.Ранее нам для определения числа шагов алгоритма часто помогал приём рассмотренияфункции λ , которая в ходе алгоритма убывала.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
