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

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

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

Если M(n) — некоторая верхняя граница для числа битовых операций, затрачиваемыхпри выполнении одной операции сложения, вычитания или умножения в Zn+1 , то сложность модифицированного таким способом алгоритма Штрассена будет допускать оценку O(nlog2 7 M(n)). Наивноеумножение в Zn+1 дает M(n) = O(log2 n). Таким образом, M(n) растет очень медленно в сравнении с остальными затратами.

Так какlog2 7 = 2,81... , мы можем использовать для сложности алгоритмаШтрассена, модифицированного на булев случай, например, оценкуe log2 7 ), — смысл «O мягкого» объяснялся в конO(n2,82 ) или оценку O(nце § .Применение алгоритма Штрассена и арифметики по модулю n + 1дает алгоритм умножения двух булевых матриц порядка n, битоваяe log2 7 ) и O(n2,82 ).сложность которого допускает оценки O(nМы ограничились рассмотрением применения стратегии «разделяй и властвуй» для случая, когда в результате этапа разделения возникают две задачи, и каждый из размеров входа примерно вдвоеменьше изначального размера. Иногда разделение приводит к треми более задачам.В  г. А. Л. Тоом обобщил идею умножения Карацубы  .

Пустьs — большее единицы целое. Предполагая, что битовая длина m каждого из сомножителей имеет вид sk , k ∈ N, последовательность двоичных цифр каждого из сомножителей можно разбить на s групп поsk−1 цифр. Тоом показал, что умножение исходных чисел сводитсяк 2s − 1 умножениям чисел битовой длины sk−1 (в умножении Карацубы s = 2, 2s − 1 = 3), остальные затраты — сложения, сдвиги — будутограничены функцией cm, где c — зависящая от выбора s константа.Здесь этап разделения приводит к 2s − 1 задачам. Для умножения Тоома (TM) неравенство(1,если m = 1,(s) (.)TTM (m) ¶(s) m+ cm, если m > 1,(2s − 1)TTMsСм.

[], [].§ . Добавление нулейвыполненное в случае m = sk , k ∈ N, и равенство(s)(s) ⌈logs m⌉TTM(m) = TTM(s),(s)выполненное при произвольном m ∈ N+ , приводят к оценке TTM(m) == O(mlogs (2s−1) ) для битовой сложности алгоритма, использующегоразбиение на s частей. Может быть также показано, что(s)TTM(m) = Θ(mlogs (2s−1) ).(.)Очевидно,11= 1 + logs 2 + logs 1 −.logs (2s − 1) = logs 2s 1 −2s2sОтсюдаlim logs (2s − 1) = 1.s→∞Это означает, что для любого ǫ > 0 можно найти целое s ¾ 2 такое, чтоумножение Тоома с разделением на s частей (битовая длина числапредполагается равной sk , k ∈ N) будет иметь битовую сложность, допускающую оценку Θ(m1+δ ) при некотором δ таком, что 0 < δ ¶ ǫ ; разумеется, для битовой сложности этого алгоритма справедлива оценка O(m1+ǫ ).Скажем коротко об основной идее алгоритма Тоома, приводящейк неравенству (.).

Если, как предполагалось, битовая длина каждого из сомножителей a, b есть sk , k ∈ N, то последовательность двоичных цифр каждого из сомножителей a, b можно разбить на s групппо sk−1 цифр:a s−1 , ..., a1 , a0 ; bs−1 , ..., b1 , b0 .Сами сомножители a, b суть значения полиномовA(x) = a s−1 x s−1 + ... + a1 x + a0 ,B(x) = bs−1 x s−1 + ... + b1 x + b0k−1в точке x0 = 2s . Полином C(x), равный произведению A(x)B(x), естьполином степени не выше чем 2s − 2 (мы не утверждаем, что этастепень равна 2s − 2, так как возможно, что к изначально заданнымцелочисленным сомножителям спереди дописывались нули), и достаточно знать значения C(x) в 2s − 1 точках (узлах интерполяции) длятого, чтобы затем, например, с помощью интерполяционной формулы Лагранжа найти значениеC(2sk−1),(.)Глава .

Рекуррентные соотношения и сложность алгоритмовравное ab. Тоом показал, что если в качестве узлов интерполяцииx1 , x2 , ..., x2s−1 взять числа−(s − 1), −(s − 2), ..., −1, 0, 1, ..., s − 2, s − 1,рекурсивно с помощью рассматриваемого алгоритма найтиA(xi ),B(xi ), C(xi ) = A(xi )B(xi ),i = 1, 2, ..., 2s − 1,и затем, пользуясь интерполяционной формулой Лагранжа, найтизначение (.), то это приведет к (.), (.). Такое использование интерполяции заключает в себе требуемое обобщение алгоритмаКарацубы.В  г.

Шенхаге и Штрассен, основываясь на идее Тоома использования интерполяции полиномов в алгоритмах умножения целыхчисел, получили алгоритм умножения, битовая сложность которогодопускает оценку O(m log m log log m), мы уже упоминали этот алгоритм в § . Функция m log m log log m растет медленнее, чем m1+δпри любом δ > 0. Улучшение достигнуто за счет привлечения интерполяции специального вида — так называемого быстрого преобразования Фурье  . До настоящего времени результат Шенхаге—Штрассена остается рекордным. Шенхаге на основе этого алгоритма умножения предложил алгоритм  нахождения íîä(a0 , a1 ), сложность которого допускает оценку O(m log2 m log log m), где m — битовая длинабольшего числа a0 (в примере . было показано, что алгоритм Евклида имеет сложность Θ(m2 )).Необходимо сказать, что преимущества по времени выполнениярассмотренных алгоритмов перед наивным умножением и алгоритмом Евклида проявляются лишь при очень больших значениях m.С умножением матриц положение таково, что обобщения алгоритма Штрассена в духе обобщения, предложенного Тоомом для алгоритма Карацубы, до сих пор не найдено.

Используя другие идеи, Д. Копперсмит и С. Виноград в  г. предложили алгоритм со сложностьюO(n2,376 ), где n — порядок перемножаемых квадратных матриц  . Этотрезультат остается рекордным по сей день. Существует ли для любого ǫ > 0 алгоритм умножения матриц со сложностью O(n2+ǫ ) — этооткрытый вопрос.Об алгоритме Шенхаге—Штрассена см., например, [, разд. .].См., например, [, разд.

.].См. [].ЗадачиЗадачи. Игра «Ханойские башни». К горизонтальной доске приделанытри вертикальных столбика. На первый нанизано n дисков, диаметры которых убывают вверх (рис. ). Требуется, перекладывая дискиРис. . Игра «Ханойские башни». Исходное положение.по одному, расположить их в прежнем порядке на третьем столбике. Ограничение состоит в том, что больший диск никогда не можетрасполагаться над меньшим.

Разработать рекурсивный алгоритм решения этой задачи и определить его временную сложность по числуперекладываний дисков.. (Продолжение предыдущей задачи.) Требуется определитьвременную сложность алгоритма перекладывания дисков в игре «Ханойские башни» при условии, что затраты на перекладывание состолбика на столбик i-го по величине диска равна а) i; б) i 2 ; в) 2i .. Сформулировать правило нахождения частного решения рекуррентного уравнения ad y(n) + ad−1 y(n − 1) + ... + a0 y(n − d) = f (n)для случая, когда f (n) принимает постоянное значение c.. Пусть функция f (n) определена для всех n ∈ N+ и пустьa — ненулевое число. Любое определенное для всех n ∈ N решениерекуррентного уравнения y(n) − ay(n − 1) = f (n) имеет вид y(n) =nPf (k).= an y(0) +kk =1aУказание.

Индукция по n.. Для чисел Фибоначчи выполнено равенствоn = 1, 2, 3, ...nPi =1Fi = Fn+2 − 1,Указание. Решением рекуррентного уравнения y(n) − y(n − 1) = Fn , y(0) == 1, является y(n) = Fn+2 .Глава . Рекуррентные соотношения и сложность алгоритмов. Верно ли, что для любого полинома p(n) найдется полиномq(n) (оба с вещественными коэффициентами) такой, что q(n + 1) −− q(n) = p(n), и если да, то как различаются степени полиномов p(n)и q(n)?.

Найти множество всех вещественных последовательностей,удовлетворяющих рекуррентному уравнению y(n + 1) + y(n) = 0.. Вернемся к алгоритму VRec из § . Пусть 1 ¶ k ¶ n. Сколькораз при построении множества Vn будет выполнено построение множества Vk ?Ответ. Fn−k .. Найти общее решение рекуррентного равенства (.) приk = 1. Найти частное решение, удовлетворяющее условию y(0) = 0.(При k = 1 рекурсия (.) не приводит к избыточным вычислениямзначений U.).

Назовем перестановку z1 , z2 , ..., zn чисел 1, ..., n критическойдлины n, если на ней достигается максимум числа сравнений, требуемых рекурсивной сортировкой слияниями для массивов длины n.Пусть n > 1, а x1 , ..., xj⌊n/k2⌋ и ly1 ,m..., y⌈n/2⌉ суть некоторые критическиеперестановки длиныответственно,n2иn. Тогда числа z1 , z2 , ..., zn , равные, со22x1 , ..., 2x⌊n/2⌋ , 2 y1 − 1, ..., 2 y⌈n/2⌉ − 1образуют критическую перестановку длины n (рис.

).Рис. . Случай, когда при n = 7 для сортировки слияниями потребуется максимальное число сравнений.. Как выглядят критические перестановки длины 6, 7, 8 и 9, полученные с помощью предложенного в предыдущей задаче подхода?Задачи. Имеет место равенство (.).Указание. См. задачу .. (Продолжение задачи , в которой фактически в рекурсивной форме описан алгоритм построения некоторой критической перестановки длины n.) Исследовать сложности описанного алгоритмапостроения некоторой критической перестановки длины n по числу умножений на два и по числу вычитаний единицы. Предложитьнерекурсивный алгоритм (например, можно рассмотреть последовательное построение критических перестановок, длины которых сутьсоответственно 1, 2, ..., n) и исследовать его сложности по названнымоперациям..

Чему равно наименьшее n вида 2k , для которого число сравнений при рекурсивной сортировке слияниями превосходит ⌈log2 n!⌉?. Оценка (.) является следствием оценки TRS (n) = λ(n) ++ λ∗ (n) − 2.. Для сложности алгоритма бинарного поиска места элементав упорядоченном массиве обосновать рекуррентное неравенство(1, j kесли n = 1,TBS (n) ¶n+ 1, если n > 1,TBS2не прибегая к известному явному выражению для TBS (n). Из этогорекуррентного неравенства получить оценку для TBS (n).. Указать алгоритм построения пересечения n полуплоскостейai x + bi y + ci ¾ 0,i = 1, 2, ..., n,имеющий временную сложность Θ(n log n) по общему числу операций.Указание.

Пересечением будет выпуклый многоугольник (возможно, неограниченный). Опираясь на алгоритм Шеймоса—Хоя (задача ), использовать стратегию «разделяй и властвуй».. По сравнению с теоремами ., . предложения ., .представляют собой более сильные утверждения, имеющие к тому жеболее широкое применение. Используя эти предложения, получитьасимптотические оценки для(0,j kесли n = 1,l mf (n) =nnf+f+ ϕ (n), если n > 1,22при ϕ (n) = log2 n и ϕ (n) = n log2 n.Глава .

Рекуррентные соотношения и сложность алгоритмов. Рекуррентное неравенство вида (.) может иметь более одного решения, однако во всех трех случаях, предусмотренных формулой (.), по крайней мере для одного решения соответствующаяоценка из (.) является точной.. Обобщить предложенную в этой главе технику решения рекуррентных неравенств на случай, когда задача с размеромj входаnknилиразбивается на s задач, размер каждой из которых — этоsl mn, где s — некоторое натуральное число ¾ 2.

Как будут выглядетьsтеоремы ., . в этом случае?. Доказать соотношение (.).Указание. Рассмотреть количество умножений чисел битовой длины 1 впроцессе применения алгоритма Карацубы к входу размера m и показать,что G(m) является для него нижней оценкой.. а) Для любого ǫ > 0 можно указать N > 0 такое, что 3TKM (m) << TKM (2m) < (3 + ǫ )TKM (m) при всех m ¾ N.б) Для любого ǫ > 0 можно указать N > 0 такое, что 7TSt (n) << TSt (2n) < (7 + ǫ )TSt (n) при всех n ¾ N.Указание. См. (.), (.) и, соответственно, (.)..

Теоремы о рекуррентных неравенствах часто формулируютсяиначе. Например, в [] и [] теорема дается, с точностью до обозначений и используемых слов, в следующем виде. Пусть s — целое¾ 2, и при любом n вида sk , k = 1, 2, ..., вещественная функция f (n)натурального аргумента удовлетворяет неравенству nf (n) ¶ wf+ cnd ,sгде w, c, d — константы, причем w > 0, c > 0, d ¾ 0. Пусть при этомf (n) не убывает на каждом отрезке [sk−1 + 1, sk ]. ТогдаdO(n log n), если d = logs w,f (n) = O(nd ),если d > logs w,O(nlogs w ),если d < logs w.Доказать эту теорему. (Заметим, что в условии теоремы . нет требования неубывания f (n) на каждом отрезке [sk + 1, sk ], но зато требуется, чтобы, например, неравенство (.) выполнялось для всех n,а не только для n вида 2k .)Глава СводимостьВ этой главе мы рассматриваем только временную сложность алгоритмов и считаем, что размер входа — это неотрицательное целоечисло.§ .

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

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