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

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

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

Алгоритм, использующий только аддитивные операции и сравнения целых чисел для проверки того, является ли данное целое положительное n точным квадратом, может быть основан на вычислении последовательности значений 1, 1 + 3, 1 + 3 + 5, ... до появленияв ней первого большего или равного n элемента. Сложность по числуаддитивных операций и операций сравнения этого алгоритма (назоpвем его sq1 ) допускает оценку Θ( n). Сохранится ли эта оценка, еслидополнительно использовать операцию нахождения целой части половины числа (считается, что затратность этой операции такая же,как у аддитивных операций) для того, чтобы предварительно выяснять, на какую максимальную степень двойки — четную или нечетную — делится n (алгоритм sq2 )?. (Продолжение предыдущей задачи.) Пусть Tsq1 (n), Tsq2 (n) —сложности, соответственно, первого и второго вариантов рассмотренного алгоритма иTsq∗ 1 (m) =max2m−1 ¶n<2mTsq1 (n),Tsq∗ 2 (m) =max2m−1 ¶n<2mTsq2 (n),m = 2, 3, ...а) Как связаны значения функций Tsq∗ 1 (m) и Tsq∗ 2 (m)?б) Имеются ли среди оценок Θ(m), O(log m), Θ(2m/2 ), O(2m ) такие,которые верны для Tsq∗ 2 (m), и если да, то какие именно?.

Изменим в алгоритме Грэхема (пример .) этап удалениявдавленных вершин: будем обходить — возможно, многократно —против часовой стрелки вершины построенной несамопересекающейся ломаной и удалять вдавленные вершины до тех пор, пока приочередном обходе не окажется безуспешной попытка найти хотя быЗадачиодну вдавленную вершину. Сложность этого варианта рассматриваемого этапа алгоритма Грэхема есть Ω(n2 ), где n — начальное числовершин ломаной (в то время как сложность этого этапа в алгоритмеГрэхема есть O(n)).. Рассмотрим в главных чертах алгоритм Шеймоса—Хоя  построения пересечения P ∩ Q двух выпуклых многоугольников P и Qсодержащих соответственно l и m вершин.

Считаем, что многоугольники задаются массивами P1 , P2 , ..., Pl и Q1 , Q2 , ..., Qm координат своих последовательных вершин.Упорядочим множество всех абсцисс обоих многоугольников повозрастанию (для простоты считаем, что абсциссы попарно различны, хотя это и несущественно), в результате получим абсциссыa1 < a2 < ... < al +m (рис. ).

Теперь для каждого i = 1, 2, ..., l + m − 1a1a2 a3...aia i +1...a m+lРис. . Алгоритм Шеймоса—Хоя (l = 5, m = 4).строим пересечение трапеций, вырезаемых прямыми x = ai , x = ai+1в заданных многоугольниках. (В вырожденном случае такая трапеция превращается в треугольник.) Из получившихся пересеченийтрапеций можно собрать P ∩ Q, удаляя лишние вершины.Привлекая дополнительно те или иные структуры данных (массивы, списки, ...) и уточняя по мере надобности какие-то этапы алгоритма, добиться того, чтобы в итоге алгоритм (обозначим его буквами SH) имел следующие сложностные характеристики. Если размер входа — это r = l + m, то TSH (r) = Θ(r); если размер входа — это′s = max{l, m}, то TSH(s) = Θ(s); если размер входа имеет два параметраСм.

[, гл. ]. Глава . Сложности алгоритмов как функции числовых аргументов′′l и m, то TSH(l, m) = Θ(l + m) — мы рассматриваем операции сравнения и перемещения элементов, арифметические операции, как мультипликативные, так и аддитивные, все вместе. Для пространственнойсложности — SSH (r), S′SH (s) или S′′SH (l, m) в зависимости от выбора размера входа — получаем те же оценки Θ(r), Θ(s) или Θ(l + m).Указание. Если исходные многоугольники представить, например, двунаправленными списками координат последовательных вершин, то список абсцисс (a1 , a2 , ..., al+m ), a1 < a2 < ... < al+m , можно получить с временными затратами, не превосходящими c0 (l + m).При определении пространственной сложности можно заметить, что общее число вершин искомого пересечения не превосходит 3(l + m) — это следует непосредственно из самого алгоритма Шеймоса—Хоя: при построениипересечения двух трапеций может возникнуть не более двух дополнительныхвершин..

Расширить алгоритм построения вояжа в ориентированномграфе 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).Доказательство.

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

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