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

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

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

Расширить алгоритм построения вояжа в ориентированномграфе G = (V , E) с выделенной начальной вершиной v (пример .)так, чтобы помимо вояжа алгоритм выдавал также информациюо том, охватил ли вояж все ребра графа. Размер входа имеет двапараметра m = | V |, n = | E |. Для графов, не содержащих изолированных вершин, т. е.

вершин, подобных вершине 7 на рис. , сложностьрасширенного алгоритма должна быть O(n).. Задача распознавания существования и фактического построения эйлерова цикла в данном графе для ориентированного случая выглядит так: выяснить, имеется ли в данном ориентированном графецикл, проходящий по всем ребрам графа по одному разу, и если существует, то построить этот цикл. Воспользовавшись рассмотреннымалгоритмом построения вояжа (пример .), дать алгоритм решенияэтой задачи. Размер входа имеет два параметра m = | V |, n = | E |.

Дляграфов, не содержащих изолированных вершин, сложность предлагаемого алгоритма должна быть O(n).. Путник столкнулся со стеной, простирающейся бесконечнов обе стороны. Имеется дверь в этой стене, но путник не знает нирасстояния до двери, ни направления к ней. Предложить позволяющий добраться до двери алгоритм, сложность которого допускаетоценку O(n), где n — число шагов (неизвестное путнику), изначально отделяющее путника от двери.Указание.

Сумма sk = 1 + q + ... + qk , q > 1, есть величина порядка qk ,т. е. sk = Θ(qk ).. Будем считать затратностью любого построения на плоскостис помощью циркуля и линейки количество линий (окружностей илиЗадачипрямых), проводимых в ходе построения.

Рассмотрим задачу построения отрезка, длина которого равна 1/n от длины исходного отрезка,считая n размером входа. Предложить для этой задачи такой алгоритм решения, сложность которого допускает оценку O(log n). . При n = 15 возможно вычисление an с меньшим числом умножений, чем требуется бинарному алгоритму возведения в степень.. Пусть двоичная запись числа n ∈ N есть βk ... β1 β0 . Алгоритмu := 1;for i = k downto 0 dou := u · u ;if βi = 1 then u := u · a fiodвычисляет an .

Сравнить сложность этого алгоритма по числу умножений с аналогичной сложностью бинарного алгоритма возведения в степень, рассмотренного в примере ., при использовании nили соответственно m = λ(n) в качестве размера входа. (Описанныйв этой задаче алгоритм является еще одним вариантом бинарногоалгоритма возведения в степень.). Для функции l(n), определенной в конце § , выполнено l(ab) ¶¶ l(a) + l(b) − 1 для всех a, b ∈ N+ .. (Продолжение предыдущей задачи.) Можно ли утверждать, чтоl(ab) = l(a) + l(b) − 1 для всех a, b ∈ N+ ?Разбор задач на построение с точки зрения их сложности содержится, например,в [, § ].Глава Сложность в среднем§ . Понятие сложности в среднемДо сих пор мы исследовали сложность в худшем случае, теперь обратимся к сложности в среднем.

Мы ограничимся ситуацией, когда прикаждом фиксированном значении s размера входа сами соответствующие входы образуют конечное множество X s = {x : k x k = s}. Будемпредполагать, что каждому x ∈ X s приписана некоторая вероятностьPs (x):0 ¶ Ps (x) ¶ 1,и при этомXPs (x) = 1.x ∈ XsТаким образом, при каждом допустимом значении s размера входамножество X s превращается в вероятностное пространство; по умолчанию считается, что вероятность распределена равномерно:Ps (x) =1,Nsгде N s — количество элементов множества X s . Функции от sXXC AT (x)Ps (x) иC AS (x)Ps (x)x ∈ Xs(.)(.)x ∈ Xsназываются временной и, соответственно, пространственной сложностью в среднем алгоритма A.

Более подробно:Определение .. Пусть при любом допустимом значении s множество X s всех входов размера s является вероятностным пространством, в силу чего временные и пространственные затраты алгоритма A для входов x (т. е. C AT (x) и C AS (x)) размера s являются случайными величинами на X s . Сложностью в среднем называется математическое ожидание (первая или вторая сумма из (.)) соответствующейслучайной величины.§ . Понятие сложности в среднемСложность в среднем может принимать и нецелые значения, дажеесли функция затрат целочисленна.Для временной и пространственной сложности в среднем алгоритма A мы будем использовать обозначения ¯T¯A (·), S̄¯ A (·).Теорема ..

Для любого алгоритма A при любом распределениивероятностей на множестве X s , где s — некоторое допустимое значение размера k · k, сложность в среднем не превосходит сложностив худшем случае:¯T¯A (s) ¶ TA (s), S̄¯ A (s) ¶ S A (s).Доказательство. Докажем, например, первое неравенство:XX¯T¯A (s) =C AT (x)Ps (x) ¶(max C AT (x))Ps (x) =x ∈ Xsx ∈ Xsx ∈ XsX=TA (s)Ps (x) = TA (s)x ∈ XsXPs (x) = TA (s).x ∈ XsВторое неравенство доказывается аналогично.Ниже в этом параграфе мы рассмотрим временную сложность всреднем ряда алгоритмов.Пример ..

Как было уже установлено (пример .), бинарныйалгоритм возведения в степень n требует λ(n) + λ∗ (n) − 2 умножений; если в качестве размера взять m = λ(n), то сложность в худшемслучае будет равна 2m − 2. Подсчитаем сложность в среднем, привлекая m как размер входа. Всего имеется 2m−1 неотрицательных целыхбитовой длины m; если считать все эти числа равновероятными, тоискомая сложность естьmm2X−12X−111∗(λ(n)+λ(n)−2)=m−2+λ∗ (n).m− 1m− 122n=2m−1n=2m−1Первая цифра каждого из чисел битовой длины m равна 1; количество чисел, имеющих кроме старшейцифрыеще k, 0 ¶ k ¶ m − 1,m−1ненулевых двоичных цифр, равно(т. е. числу сочетаний изkm − 1 по k). Поэтому искомую сложность можно переписать в видеm−1 m−1 ‹XXm−11m−11k.m − 2 + m − 1 2 m −1 +k= m − 1 + m− 12k =1k2Легко проверяется, что при 1 ¶ k ¶ m − 1 выполненоm−1m−2k= (m − 1),kk−1k =1kГлава .

Сложность в среднеми возможно дальнейшее упрощение выражения для сложности:m−1+m−12 m− 1m−1Xk =1m−2k−1=m−1+m−12 m− 1m−2Xl =0m−2l32= (m − 1).Если рассматривать m = λ(n) как размер входа бинарного алгоритма вычисления an , n ∈ N+ , то сложность в среднем по числу умно3жений для этого алгоритма есть (m − 1).2Таким образом, при больших m сложность в среднем бинарногоалгоритма возведения в степень приблизительно равна трем четвертым сложности в худшем случае.Анализ сложности в среднем для широкого ряда арифметическихалгоритмов опирается на асимптотический закон распределения простых чисел, который мы приведем без доказательства.Асимптотический закон распределения простых чисел.

Дляфункции π(n), значение которой равно количеству простых чисел,меньших данного натурального n, справедливо асимптотическое равенствоnπ(n) ∼.(.)ln nКак следствие, вероятность того, что при выборе «наугад» одногоиз целых чисел 1, 2, ..., n попадется простое число, асимптотически1 равна.ln nПример .. Вновь вернемся к алгоритму пробных делений, предназначенному для распознавания простоты данного n ¾ 2 (примеры ., .). Будем рассматривать в качестве размера входа битовуюПредположение о справедливости этого закона распределения простых чисел высказывалось, в частности, Гауссом и Лежандром. Впоследствии в  г.

Чебышевымбыло доказано, что для некоторых констант c и Ccnln n< π(n) < Cnln nдля всех достаточно больших n, и, более того, им было установлено, что можно положить C = 1,10555, c = 0,92129. Асимптотическое равенство (.) было полностью доказано в  г. независимо Ж. Адамаром и Ш. Валле Пуссеном. «После доказательстванеравенств Чебышева в  г. речь шла, казалось бы, только о более точном нахождении и сближении постоянных c и C. Однако асимптотический закон распределенияпростых чисел был доказан лишь полвека спустя, в самом конце XIX века, на основании совершенно новых идей, предложенных Риманом...» [].

В [, гл. V] приводится1элементарное доказательство неравенств Чебышева для C = 6 и c = . Полное доказательство асимптотического закона имеется, например, в [].3§ . Понятие сложности в среднемдлину m данного числа. На первый взгляд сложность в среднем этогоалгоритма могла бы оказаться существенно меньшей, чем сложностьв худшем случае, так как для многих входов затраты совсем невелики.Например, для четных входов достаточно одного деления и т.

д. Длясложности в худшем случае по числу делений нами была установлена экспоненциальная оценка Θ(2m/2 ). Существует ли d ∈ N такое, чтосложность в среднем алгоритма пробных делений как функция от mдопускает оценку O(md )? Мы видим, что для довольно обширногомножества входов размера m алгоритм пробных делений работаетбыстро, и предположение, что для сложности в среднем существуеттакое число d, выглядит правдоподобным.

На самом деле все обстоит не так, потому что среди всех натуральных чисел доля простых(для которых алгоритм пробных делений работает долго) достаточновелика. Оценка количества V (m) простых среди чисел2 m −1 ¶ n < 2 mможет быть получена из приведенной выше теоремы о распределениипростых чисел: воспользовавшись тем, чтоπ(2m ) ∼2m,(ln 2)mm → ∞,а также равенством V (m) = π(2m ) − π(2m−1 ), получимV (m) ∼11m−22m ∼2m .2 ln 2 m(m − 1)(2 ln 2)m(.)Теперь уже экспоненциальность роста сложности в среднем алгоритма пробных делений выводится легко.

Обозначим через D(n)количество делений, требующееся алгоритму пробных делений применительно к натуральному числу n. Для любого простого p ¾¾ 2m−1 , m ¾ 7, выполнено D(p) > 2m/2−1 (в самом деле, D(p) =p= ⌊ p ⌋ − 1 ¾ ⌊2(m−1)/2 ⌋ − 1 > 2(m−1)/2 − 2, и при m ¾ 7 выполнено2(m−1)/2 − 2 ¾ 2m/2−1 ). Интересующая нас сложность в среднем рав2m−1P1D(n). При m ¾ 7 мы имеемна m−12n=2m−112m− 1m2X−1n=2m−1D(n) ¾12m− 1Xm−1D(p) ¾ V(m)2−m/2 .(.)m2¶ p <2p — простоеУчитывая (.), находим, что последняя величина при m → ∞ асимптотически равна12m/2 .(2 ln 2)mГлава . Сложность в среднемЭто говорит о том,чтоисследуемая сложность по числу делений1 m/2и как функция от m эта сложность не мо2в среднем есть Ωmжет быть оценена как O(md ) ни при каком d ∈ N.Определение ..

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

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