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

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

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

Функция f (x) = 2явля∗ется возрастающей, и по теореме . из TTD(m) = O(2m/2 ) следуетpTTD (n) = O(2(log2 n+1)/2 ) = O( n). Рассматривая возрастающую функpцию g(x) =p x, мы можем, применивтеорему .(i), вывести изp∗TTD (n) = O( n) оценку TTD(m) = O( 2m ) = O(2m/2 ).p∗Получить из оценки TTD(m) = Ω(2m/2 ) оценку TTD (n) = Ω( n) мыне можем, так как последняя оценка не верна; это не противоречитдоказанным утверждениям.Пример .. Идея бинарного алгоритма возведения a в целуюнеотрицательную степень n, называемого также алгоритмом повторного возведения в квадрат (мы будем обозначать его буквами RS, отанглийского названия алгоритма repeated squaring — повторное возведение в квадрат), состоит в том, что если двоичная запись n естьβk ...

β1 β0 , то вычисление an может быть сведено к вычислению послеiдовательности значений qi = a(2 ) , i = 0, 1, ..., k (каждый следующийэлемент последовательности получаем возведением в квадрат преды-§ . Длина числа как возможный размер входадущего), и подсчету произведения u тех qi , для которых βi = 1:q := a; u := 1;for i = 0 to k − 1 doif βi = 1 then u := u · q fi;q := q 2odu := u · qНапример, a11 = a8 · a2 · a ( умножений), так как (11)10 = (1011)2 .Займемся сложностью по числу умножений этого алгоритма. Используя λ(n) для обозначения битовой длины n и обозначение λ∗ (n)для числа единиц в двоичной записи n, мы легко получаем следующее.Если рассматривать n как размер входа бинарного алгоритма вычисления an , n ∈ N+ , то сложность TRS (n) по числу умножений дляэтого алгоритма равна λ(n) + λ∗ (n) − 2.

Если в качестве размера вхо∗да рассматривать m = λ(n), то сложность TRS(m) по числу умножений равна 2m − 2.∗Для TRS(m) и TRS (n) имеем очевидные асимптотические оценки∗TRS(m) = Θ(m),TRS (n) = Θ(log n).∗Заметим, что мы не можем вывести из TRS(m) = 2m − 2 равенство∗TRS (n) = λ(n) + λ (n) − 2, хотя обратный вывод очевиден.В рассмотренном алгоритме предполагается, что показатель степени n задан как массив двоичных цифр.

Если показатель n задан какчисло, то его двоичные цифры β0 , β1 , ... могут быть получены одназа другой нахождением соответствующих частных и остатков от деления на 2. Это не изменит оценок Θ(log n), Θ(m) как для общегочисла операций, так и для числа мультипликативных операций. Нопри этом бинарный алгоритм возведения в степень может быть использован, например, для вычисления An , где A — матрица большогопорядка и т.

д. В этом смысле те операции, которые подразумеваются в командах u := u · q и q := q 2 , естественно подсчитывать отдельнои именно их считать составляющими главные затраты алгоритма.Задачу вычисления an в некотором множестве с ассоциативнымумножением (т. е. в полугруппе) часто формулируют как задачу об аддитивных цепочках для n, т. е.

о наборах целых чисел n1 < n2 < ... < nk ,в которых• n1 = 1, nk = n;• для каждого i, 1 < i ¶ k, найдутся s, t такие, что 1 ¶ t ¶ s < i и nt ++ n s = ni . Глава . Сложности алгоритмов как функции числовых аргументовКаждая аддитивная цепочка для n задает способ вычисления an . Например, аддитивная цепочка 1, 2, 3, 4, 8, 11 для 11 задает тот способ, который соответствует бинарному алгоритму возведения в степень. Задача быстрого возведения в степень n с помощью умножений — это фактически задача построения короткой аддитивной цепочки для n.Обозначение l(n) закреплено за длиной самой короткой аддитивной цепочки для n. Бинарный алгоритм возведения в степень использует свою специфическую аддитивную цепочку (назовем ее бинарной).

Бинарная цепочка не для всех n имеет длину l(n) (см. задачу ). Но, как мы выясним несколько позже, длина бинарной цепочки и l(n) имеют одинаковый порядок. Помимо этого бинарныецепочки легко и быстро строятся, чего в общем случае нельзя сказать об аддитивных цепочках длины l(n).Некоторые предположения относительно функции l(n) до настоящего времени не доказаны, хотя и подтверждены проверкой для многих n.

К числу таковых относится, например, гипотеза Шольца—Брауэра: l(2n − 1) ¶ n − 1 + l(n) для всех n > 0. Задачиj k l mnn+, для любого a ∈ R. Для любого n ∈ Z выполнено n =22выполнено ⌈a⌉ = −⌊−a⌋.. Для любых k, n ∈ N+ , k > 1, выполнено ⌊logk n⌋ + 1 = ⌈logk (n + 1)⌉.Указание. Пусть m ∈ N+ таково, что km−1 ¶ n < km , тогда km−1 < n + 1 ¶ km .Прологарифмировать по основанию k обе системы неравенств.. Предположим, что в нашем распоряжении нет операции обменаa ↔ b и мы заменяем ее тремя присваиваниями:c := a;a := b;b := c;чему в этом случае равны сложности первого и второго варианта сортировки простыми вставками по суммарному числу сравнений и присваиваний?.

Пусть полином f (n) = am nm + ... + a1 n + a0 имеет ненулевойстарший коэффициент am . Тогдаа) f (n) = O(nk ) ⇔ k ¾ m,б) f (n) = Ω(nk ) ⇔ k ¶ m,в) f (n) = Θ(nk ) ⇔ k = m, при k = m также выполнено f (n) ∼ am nm .Подробнее об аддитивных цепочках см. в [, разд. ..].Задачи. Пусть P(n) — количество простых множителей целого числаn > 1 с учетом кратности. Имеет место точная оценка P(n) = O(log n).. (Продолжение предыдущей задачи.) ПустьP ∗ (m) =max2m−1 ¶n<2mP(n),m = 2, 3, ... Верно ли, что P ∗ (m) = Θ(m)?. Указать все вещественные значения δ, при которых справедливаоценкаа) TTD (n) = O(nδ ),б) TTD (n) = Ω(nδ ),в) TTD (n) = Θ(nδ ),где TTD (n) — сложность алгоритма пробных делений (пример .)..

Железнодорожный сортировочный узел устроен так, как показано на рис. . На правой стороне собрано некоторое число вагоновМИМОИЗВтупикРис. . Сортировочный узел.двух типов (на рис.  — черные и белые), по n штук каждого типа. Тупик может вместить все 2n вагонов. Требуется, пользуясь тремя сортировочными операциями В, ИЗ, МИМО, собрать вагоны на левой стороне так, чтобы типы вагонов чередовались. Указать такой алгоритмрешения этой задачи, сложность которого по числу сортировочныхопераций при рассмотрении n в качестве размера входа равнялась бы3n − 1.. Хорошо известно, что мультипликативная сложность методаГаусса решения системы n линейных уравнений с n неизвестнымидопускает оценки) O(n3 ),)1 3n + O(n2 ),3) Θ(n3 ). Глава .

Сложности алгоритмов как функции числовых аргументова) Из какой оценки (указать номер) следуют две остальные?б) Можно ли из приведенных оценок выбрать такую, которая является следствием любой из остальных?в) Является ли оценка Ω(n3 ) следствием какой-либо из оценок ,, ?. Для сложности TQS (n) быстрой сортировки выполняется оценкаTQS (n) = Θ(n2 ). (Обозначение QS происходит от английского названиябыстрой сортировки — quick sort.)Указание. Оценка TQS (n) = Ω(n2 ) устанавливается предъявлением примера. Неравенство TQS (n) < n2 можно доказать индукцией по n, используя то,что при фиксированном n ∈ N+ квадратичная функция (m − 1)2 + (n − m)2от m принимает на отрезке [1, n] свое максимальное значение в одном изконцов этого отрезка..

Алгоритм, использующий только аддитивные операции и сравнения целых чисел для проверки того, является ли данное целое положительное 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) — это следует непосредственно из самого алгоритма Шеймоса—Хоя: при построениипересечения двух трапеций может возникнуть не более двух дополнительныхвершин..

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

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