С.А. Абрамов - Вычислительная сложность алгоритмов, страница 6

Тогда справедливо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!Согласно этому утверждению, сортировка фон Неймана и сортировка бинарными вставкамибудут оптимальными по порядку сложности в среднем.Ранее нам для определения числа шагов алгоритма часто помогал приём рассмотренияфункции λ , которая в ходе алгоритма убывала. Для асимптотической сложности в среднемтоже могут применяться подобные методы.Пусть на некотором вероятностном пространстве задана последовательность случайныхвеличин ξ1 , ξ 2 , ...

и числовая последовательность h1 , h2 , ... такая, что выполнено неравенство:n⎧⎫E(ξ k ξ1 , ..., ξ k −1 ) ≤ hk . Зафиксируем q ≥ 0 и рассмотрим цело число τ = min ⎨n : ∑ ξ k ≥ q ⎬ .⎩ k =1⎭τ⎛⎞Тогда E⎜ ∑ nk ⎟ ≥ q .⎝ i=1 ⎠Этот факт позволяет доказывать, что число шагов алгоритма ≥ q .Для алгоритма поиска максимального и минимального элемента массива асимптотическаяоценка снизу сложности в среднем равна:⎧3⎪⎪ 2 n − 2, если n - чётноеf ( n) = ⎨⎪ 3 n − 2 + 1 , если n - нечётное2n⎩⎪ 229Битовая сложностьКогда мы занимались алгебраической сложностью, при её исследовании мы считалибитовую длину операндов не важной, за исключением случаев, когда в качестве размеравхода выбиралась битовая длина.

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

Работа эта более кропотливая и детальная, поэтому ограничимсяарифметическими операциями.На первый взгляд кажется, что если мы хотим исследовать битовую сложность какого-тоалгоритма, то нам нужно переписать его в битовых операциях. Но никто так не делает.Вместо этого полагают наличие соответствующих арифметических процедур (сложение,вычитание и т.д.).Рассмотрим целую арифметику. Будем считать, что числа заданы в двоичном виде.Итак, у арифметической операции 2 аргумента: a и b.

Что в этом случае считать размеромвхода? Возможны следующие варианты: 1) размером входа можно считать сами числа a и b;2) битовую длину операндов: ma = ν (a ) ; mb = ν (b) ; 3) m = max{ma , mb } ; 4) ma + mb .Операция сложения (Add).Для затрат битового сложения справедлива оценка:Tmin{ma , mb } ≤ C Add(a, b) ≤ c(max{ma , mb }+ 1)где c — некоторая постоянная, не зависящая от a и b. Действительно, для сложениястолбиком на каждом этапе, исходя их 3-х бит на входе (слагаемые и возможный перенос),нужно получить 2 бита (результат и перенос), откуда следует оценка сверху. Оценка снизутоже понятна, т.к. мы должны поработать с каждым битом меньшего числа.*Получим асимптотику для сложности в следующем виде: TAdd(m) = Θ(m) .

Для этогодостаточно доказать соответствующие оценки снизу и сверху. Оценка сверху следует извышеприведённой оценки для затрат, а для оценки снизу можно взять два числа содинаковой длинной: ma = mb . Тогда min{ma , mb } = max{ma , mb } , и в силу оценки для затратполучаем требуемую оценку снизу для сложности.Для пространственной сложности получаем следующие оценки: в случае формирования*результата на месте большего числа — S Add(m) = O(1) ; в случае формирования результата на*новом месте — S Add(m) = m + O(1) .Алгоритмы умножения через сложение и деления через вычитание будем называть«наивными».Пример.«Сверхнаивное» умножение.