С.А. Абрамов - Вычислительная сложность алгоритмов (1123766), страница 11
Текст из файла (страница 11)
< 3 .Вернёмся к алгоритму Карацубы: если разбиваем на 2 части, то нужно 3 умножения.Возникает идея: можно ли разбивать на p частей, чтобы требовалось q умножений чиселlog qменьшей длины ( Θ n p )? В алгоритме Карацубы p = 2 , q = 3 . Можно ли подобрать p и qтак, чтобы log был ещё меньше? Ответ на этот вопрос дал А.Л.Тоом, который показал, чтодля любого p можно предложить алгоритм разбиения чисел длины p k на части p k −1 и()(использующий 2 p − 1 умножений: Θ nlog p ( 2 p −1)). Обратим внимание на следующее:⎛⎛⎛1 ⎞1 ⎞1 ⎞⎟⎟ = log p 2 p + log p ⎜⎜1 −⎟⎟ = 1 + log p 2 + log p ⎜⎜1 −⎟⎟log p (2 p − 1) = log p 2 p⎜⎜1 −⎝ 2p ⎠⎝ 2p ⎠⎝ 2p ⎠Последние 2 слагаемых приведённого равенства с ростом p стремятся к нулю, поэтомуlog p (2 p − 1) → 1 при p → ∞ , т.е.
∀ε > 0 ∃ алгоритм умножения со сложностью Ο(n1+ε ) .Отметим, что Штрассену удалось из других соображений предложить метод умножения,допускающий оценку O(n log n log log n ) , которая лучше полученной.Тоом в своём методе «резал» числа более чем на 2 части. Казалось бы, что для матрицможно применить такой же подход и получить оценку вроде O(n 2+ε ) .
Оказывается, чтоничего подобного. Но останавливаться на этом факте мы здесь не будем.Отметим, что в литературе по теории сложности указывается более короткий путь анализасоотношений, получаемых из алгоритмов, действующих по принципу «разделяй и властвуй».На этот счёт формулируется соответствующая теорема, часто называемая master theorem. Кпримеру, в пособии В.Б.Алексеева эта теорема формулируется следующим образом:Теорема (о рекуррентном неравенстве).
Пусть f (n) — функция натурального аргумента,пусть C — натуральное число, C ≥ 2 , и a, b, α — вещественные константы, причём α > 0 ,и пусть для всех n вида Ck, k = 1, 2, ... выполнено неравенство⎛n⎞f (n) ≤ af ⎜ ⎟ + bnα⎝C ⎠[]Пусть при этом f (n) монотонно не убывает на каждом отрезке вида C k + 1, C k +1 . Тогда приn → ∞ для всех n выполняется46( )( )()⎧O nα , α > log C a⎪f (n = ⎨O n logC a , α < log C a⎪ α⎩O n log n , α = log C aПосмотрим, даёт ли нам эта теорема что-то новое.
Пусть C = 2 , тогда n = 2 k иассоциированным уравнением для рекуррентного неравенства из условия теоремы будетt (k ) = a ⋅ t (k − 1) + b ⋅ (2k )αили, что то же самое,t (k ) = a ⋅ t (k − 1) + b ⋅ (2α ) .kКорнем соответствующего характеристического уравнения будет λ = a и дальнейшеерешение рекуррентного соотношения будет зависеть от того, совпадает ли 2α с a, чтоэквивалентно равенству α = log 2 a . Так, если α ≠ log 2 a , то, учитывая доминанты, получимпервые 2 строчки утверждаемого соотношения.
Тем самым убеждаемся, чтосформулированное ранее предложение весьма схоже с этой теоремой.Всё это получается для чисел вида 2 k . Если переходить к общему случаю, то, используямонотонность, нужно рассматривать на одном из концов отрезка. Но монотонность не всегдаочевидна, поэтому в этом вопросе следует проявлять осторожность (уже рассматривалсяпример сложности алгоритма возведения в степень RS, которая не обладает монотонностью).И ещё: теорема даёт оценку сверху, а для сравнения алгоритмов, только оценки сверху недостаточно.47СводимостьПусть имеются две задачи P и Q. Под «задачей» будем понимать следующую пару:1) вычислительное задание;2) соглашения о размере входа и о том, в чём измеряются вычислительныезатраты.Размер входа будем в дальнейшем всегда считать целым неотрицательным числом,сложность всегда будем считать однопараметрической функцией.
Заметим сразу, чтосформулированные допущения нас вовсе не обременяют.Определение. Будем говорить, что задача P не сложнее Q, если для любого алгоритма AQ ,решающего задачу Q найдётся алгоритмTAP (n) = O TAQ (n) .()AP , решающий задачу P, такой, чтоОбозначение: P ≤ Q .Отметим сразу, что это бинарное отношение транзитивно. И ещё одно важное дополнение:жизнь не столь проста, как кажется. Определением, сформулированным выше, на практикеприходится пользоваться редко. В связи с этим принимаются дополнительные соглашения осложностях рассматриваемых алгоритмов, которые мы сформулируем ниже, а пока ихобозначим.
Оговаривается, что сложности растут не слишком медленно и не слишкомбыстро. Эти соглашения иногда доказуемы, иногда выводятся из правдоподобности. Такжене рассматриваются «второсортные» алгоритмы, т.е. «на каждый хороший алгоритмрешения задачи Q найдётся хороший алгоритм, решающий задачу P».Определение. Задачи P и Q, для которых одновременно верно P ≤ Q и Q ≤ P , будемназывать эквивалентными (по сложности).Обозначение: P >< Q .Далее рассмотрим пример.Пример. Раньше про деление мы почти ничего не говорили, кроме того, что его можнореализовать на базе умножения.
Рассмотрим следующие задачи:M:умножение 2-х целых чисел a и bD:деление целого a битовой длины ≤ 2m на целое b битовой длины mS:возведение в квадрат целого aR:обращение целого aВ задаче R имеется в виду не точное вычисление, а до m двоичных разрядов послезапятой. Для задачи D — построение m двоичных цифр частного, не зависимо отположения запятой.Покажем, что M >< D >< S >< R .Для начала сформулируем ограничения, которые будем предполагать выполненными:1) сложность любого из рассматриваемых алгоритмов f (m) является неубывающейфункцией;2) для сложности верно f (m) ≥ m (растёт не слишком медленно);3) для f (αm) верно: αf (m) ≤ f (αm) ≤ α 2 f (m) , для любого вещественного α > 1 .48Полное доказательство мы здесь приводить не будем (его можно найти в книге«Построение и анализ вычислительных алгоритмов» из рекомендуемой литературы) ирассмотрим его лишь в общих чертах.Начнём с того, что докажем M ≤ S .
Для этого нужно показать, что для любогоалгоритма AS , решающего задачу S, найдётся алгоритм AM , решающий задачу M,такой, что будет выполнена оценка: TAM (m) = O TAS (m) .()()1(a + b )2 − a 2 − b 2 . Это соотношение2даёт нам алгоритм вычисления произведения, используя операцию возведения встепень. Очевидно, что сложение и вычитание имеет линейную по времени сложность,а деление на 2 вообще выполняется за даром (деление на 2 эквивалентно сдвигу всехразрядов числа на 1 бит вправо). Поэтому для сложности такого алгоритма получаем:Воспользуемся следующим соотношением: ab =TAM (m) = TAS (m + 1) + 2TAS (m) + O(m)12314243" + " и "− "( a +b ) 21)3)TAS (m + 1) ≤ TAS (2m) ≤ 4TAS (m) (в силу сформулированных ограничений 1 и 3)()⇒ TAM (m) = O TAS (m) .Теперь докажем, что S ≤ R . Будем считать, что у нас есть алгоритм AR , решающийзадачу R — обращения целого числа.
Воспользуемся равенством:a2 =111−a a +1−aЗаметим, что в итоге мы должны получить целое число ( a 2 ), в то время как в правойчасти равенства стоят совсем не целые величины. Дотошные авторы в умных книжкахговорят, что в обращении надо брать 3m цифр после запятой. Умножаем на 23m ,получая целое число, и обращаем. Затем, глядя на последние 4 цифры, можно получитьцелый ответ, сделав некоторую поправку.
TAS (m) = O TAR (3m) и с учётом пункта 3()()ограничений, получаем TAS (m) = O TAR (m) .Покажем, что R ≤ M . В этом случае одной формулой обойтись не получится ипридётся привлечь математический анализ. Построим последовательность x0 , x1 , x2 , ... ,1сходящуюся к . Такую последовательность, например, можно описать рекуррентнойaформулой: xi = 2 xi−1 − axi2−1 . Соотношений такого рода можно привести не одно, ноособенностью такой формулы является то, что она родственна с методом касательныхрешения уравнения на отрезке (если сходится, то очень быстро: сходимостьквадратичная, а не линейная).
Кроме того, исследуя несколько первых цифр числа a,11можно выбрать x0 так, что≤ x0 ≤ и для элементов последовательности будет2aa11выполнено: xi = (1 − ε ) , xi+1 = (1 − ε 2 ) . С учётом нулевого приближения, дляaa11элементов последовательности будет верно, что xi − ≤ 2i . У приближенийa 2отбрасываем концы (те цифры, которые не заслуживают доверия). Используя тот факт,49что сумма геометрической прогрессии имеет порядок последнего члена, получаем, чтоTAR (m) = O TAM (m) .()Тем самым доказано, что M ≤ S ≤ R ≤ M ⇒ M >< S >< R .Следующим этапом покажем, что D ≤ M , используя, что M >< R .
Будем исходить изa1того, что = a ⋅ . Деление в этом случае будет неточным, поэтому надо выполнитьbbделение с запасом ( 3m ), после чего умножить. При этом младшие разряды могутоказаться неверными. Дотошные люди посчитали, что их количество не превосходит 3,и «шевелением» этих разрядов можно получить точный ответ. Осталось показать, чтоR ≤ D , но это очевидно.Определение. Пусть существуют 2 задачи P и Q и 2 алгоритма U и V такие, что алгоритм Uпо входу задачи P строит один или несколько входов для задачи Q:Uy1 , ... , yk — входы Qx — вход P ⎯⎯→Задача Q переводит y1 , ... , yk в z1 , ...
, zk : Q( y1 , ... , yk ) → z1 , ... , zk , а алгоритм V по z1 , ... , zkстроит решение задачи Q. Тогда пару (U , V ) будем называть сведением.Отвлечёмся на минуту от сведений и докажем общее утверждение.Утверждение. Если P и Q таковы, что P ≤ Q , P и Q — классы алгоритмов, решающихзадачи P и Q соответственно, и пусть f (n) — асимптотическая нижняя граница сложностидля класса P. Тогда f (n) будет являться асимптотической нижней границей сложности длякласса Q.(Доказательство: P ≤ Q ⇔ TAP (n) = O TAQ (n))()⇔ TAQ (n) = Ω TAP (n) . С другой стороны,f (n) является асимптотической нижней границей для P ⇒ ∀A ∈ P (в частности, дляA = AP ) будет верна оценка: TA (n) = Ω( f (n) ) ⇒ TAP (n) = Ω( f (n) ) ⇒ TAQ (n) = Ω( f (n) ) , чтодоказывает утверждение.Пример.
Вернёмся к задаче построения выпуклой оболочки. Покажем, что если за размеравхода взять n — количество данных точек на плоскости, то Ω(n log n) будет нижнейасимптотической оценкой. Отметим, что «продвинутые» алгоритмы построениявыпуклой оболочки имеют оценку сложности O(n log n) , тем самым являютсяоптимальными по порядку сложности. Как показать Ω(n log n) ? Для этого сведёмалгоритм сортировки к задаче о построении выпуклой оболочки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
