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

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

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

Предположим, что имеется несколько целых чисел a1 , a2 , ..., an ,каждое из которых ¾ 2, и с помощью пошаговых наивных умноженийa1 a2 , (a1 a2 )a3 ,...,(a1 a2 ...an−1 )an(.)вычисляется произведение A = a1 a2 ...an . Пусть суммарная битоваядлина чисел равна M, и число M рассматривается как размер входа алгоритма (.). Покажем, что тогда битовая сложность этогоГлава . Битовая сложностьалгоритма допускает верхнюю оценку O(M 2 ), — примечательно, чточисло n, т. е. общее количество сомножителей, в этой оценке не появляется.В силу предложения . и неравенства (.) битовые затраты навычисление a1 , a2 , ...an не превосходит cF(a1 , a2 , ..., an ), где c — некоторая положительная константа, а значение F(a1 , a2 , ..., an ) равноlog2 a1 log2 a2 + log2 (a1 a2 ) log2 a3 + ... + log2 (a1 a2 ...

an−1 ) log2 an(использовано предположение, что a1 , a2 , ..., an ¾ 2). Мы легко получаемF(a1 , a2 , ..., an ) ¶ log2 (a1 ... an−1 )(log2 a2 + ... + log2 an )иF(a1 , a2 , ..., an ) ¶ (log2 a1 + log2 a2 + ... + log2 an )2 .Последнее неравенство позволяет перейти к рассмотрению M в качестве размера входа, так как, очевидно,2F(a1 , a2 , ..., an ) ¶ ⌈log2 (a1 + 1)⌉+⌈log2 (a2 + 1)⌉+ ...+⌈log2 (an + 1)⌉ = M 2 ,что дает нам требуемое.Доказанное утверждение справедливо и в том случае, когда среди a1 , a2 , ..., an имеются единицы, если считать, что умножение на 1требует одной битовой операции. Если среди a1 , a2 , ..., an имеютсяk единиц, то из M ¾ k следует (M − k)2 + k ¶ M 2 .§ . Наивная арифметика: деление с остаткомОбратимся к наивному делению с остатком. Здесь мы считаем, чтоm = m1 ¾ m2 .∗Предложение ..

Пусть TND(m) — сложность по числу битовыхопераций наивного деления при использовании m в качестве разме∗∗ра входа. Пусть TND(m1 , m2 ) — сложность по числу битовых операцийэтого же алгоритма при использовании m1 , m2 в качестве двух параметров размера входа. Тогда∗TND(m) = Θ(m2 ),∗∗TND(m1 , m2 ) = Θ((m1 − m2 + 1)m2 ).(.)Доказательство. Наивное деление a на b сводится к ряду вычитаний числа b, и в каждом вычитании битовая длина уменьшаемого либо равна, либо на единицу превосходит m2 . Битовые затраты на каждое такое вычитание не могут превзойти, как мы знаем, c(m2 + 1). Количество всех таких вычитаний не превосходит∗∗m1 − m2 + 1, откуда TND(m1 , m2 ) = O((m1 − m2 + 1)(m2 + 1)) и, после§ .

Наивная арифметика: деление с остатком∗∗упрощения, TND(m1 , m2 ) = O((m1 − m2 + 1)m2 ) (см. задачу ). С другой стороны, если, например, a = 2m1 − 1, b = 2m2 −1 , то число вычитаний равно m1 − m2 + 1, и, как следствие, битовые затраты нанаивное деление будут не меньше, чем (m1 − m2 + 1)m2 . Поэтому∗∗TND(m1 , m2 ) = Θ((m1 − m2 + 1)m2 ).∗Оценка TND(m) = O(m2) следует теперь из неравенства m2 ¾ m1 m2 ¾¾ (m1 − m2 + 1)m2 . Если взять a = 2m − 1, b = 2⌊m/2⌋j, тоk битовыезатраj kmm+1+1 ,ты на наивное деление будут не меньше чем m −2∗∗и, как следствие, TND(m) = Ω(m2 ). Получаем TND(m) = Θ(m2 ).2∗∗Мы не пишем TND(m1 , m2 ) = Θ((m1 − m2 )m2 ) из-за возможности равенства m1 = m2 (из которого не следует, что a = b).

Эта возможность∗∗указывает и на то, что неверно соотношение TND(m1 , m2 ) = Θ(m1 m2 ).Предложение .. При использовании самих положительных целых a, b, a ¾ b > 1, в качестве параметров размера входа, сложностьнаивного деления a на b допускает оценку O(log a log b). При использовании a в качестве размера входа имеем оценку O(log2 a).Доказательство. Как уже говорилось, число битовых операций,требуемых наивным умножением, не превосходит произведенияc (⌊log2 a⌋ + 1) − (⌊log2 b⌋ + 1) + 1 (⌊log2 b⌋ + 1)(c — положительная константа), которое не превосходит в свою очередьc(log2 a − log2 b + 2)(log2 b + 1).Каждое слагаемое, возникающее в результате раскрытия скобок в последнем выражении, есть O(log a log b) при a, b → ∞, a ¾ b. Отсюдаследует первая часть утверждения.

Вторая часть следует из того, чтоlog2 a log2 b ¶ log22 a при a ¾ b.Пример .. Пусть n и k — положительные целые числа, k ¾ 2,заданные в двоичной системе счисления. Покажем, что при избрании n в качестве размера входа n, k (равно как и при избрании n, kв качестве двух параметров размера этого входа) битовая сложностьобычного алгоритма построения k-ичной записи числа n с помощьюнаивных делений с остатком допускает оценку O(log2 n).В самом деле, при построении k-ичной записи n шаг за шагомj q расkсматриваются числа q0 , q1 , ..., qt , t = ⌊logk n⌋ + 1, где q0 = n, qi = i−1 ,ki = 1, 2, ..., t.

Очевидно, что qi ¶ n, в силу чего общие затраты всех шагов для данных n и k допускают оценку O(log n log k logk n). Очевидно,log k logk n = log n (например, log2 k logk n = log2 n), поэтому оценка дляГлава . Битовая сложностьзатрат переписывается в виде O(log2 n); при указанных выше размерахвхода эта оценка является и оценкой сложности.Вновь вернемся к обозначению m для битовой длины максимального из двух данных целых положительных чисел, и пусть m рассматривается как размер входа a, b алгоритмов умножения и деленияс остатком.

Для сложностей наивного умножения и деления мы получили оценки Θ(m2 ), следствием которых являются нижние оценкиΩ(m2 ). Вместе с этим, для умножения и деления известны алгоритмы, сложности которых при m → ∞ растут существенно медленнее,чем m2 : первый алгоритм такого рода для умножения был предложенв  г.

А. А. Карацубой (верхняя оценка O(mlog2 3 )), наилучшую изизвестных к настоящему времени верхнюю асимптотическую оценкубитовой сложности O(m log m log log m) имеет алгоритм А. Шенхагеи Ф. Штрассена. Существуют алгоритмы деления, сложность которыхдопускает такие же оценки (см. задачу  к главе ).

Алгоритм Карацубы будет рассмотрен нами в § , алгоритм Шенхаге—Штрассенав этом курсе подробно не рассматривается; несколько слов о нем будет сказано в конце § .Пример .. Исследуем битовую сложность алгоритма Евклида.В качестве размера входа можно рассмотреть большее число a0 , нони в коем случае не a1 : если фиксировано a1 , то, неограниченно увеличивая a0 , мы будем неограниченно увеличивать битовые затраты,связанные с первым делением с остатком (a0 на a1 ). Поэтому при выборе a1 в качестве размера входа битовая сложность этого алгоритматождественно равна бесконечности — здесь битовая сложность существенно отличается от алгебраической (т. е.

в данном случае от сложности по числу делений). Можно считать a0 размером входа, а можнорассмотреть два параметра a0 , a1 размера входа. Если m0 , m1 — битовые длины данных чисел a0 , a1 , то в качестве размера входа можно рассмотреть m = max{m0 , m1 } = m0 или же два параметра входаm0 , m1 . В настоящем примере мы будем использовать m.Прежде всего покажем, что для алгоритма Евклидаa i −1 = q i a i + a i +1 ,i = 1, 2, ..., n,an+1 = 0,выполняетсяa0 ¾ q1 q2 ...qn .(.)В самом деле,a0 > q1 a1 ,a1 > q2 a2 , ...,a n −2 > q n −1 a n −1 ,и получаем a0 ¾ q1 q2 ...qn an , откуда следует (.).a n −1 = q n a n ,§ . Наивная арифметика: деление с остаткомДля построения ai+1 делением ai−1 на ai с остатком требуется неболее c(⌊log2 qi ⌋ + 1)(⌊log2 ai ⌋ + 2) битовых операций, где c — положительная константа.

Это дает общую оценку сверхуnX(⌊log2 qi ⌋ + 1)(⌊log2 ai ⌋ + 2),ci =1при этом возможно, что некоторые из qi равны единице. Написаннаясумма не превосходитnXc(⌊log2 a1 ⌋ + 2)(⌊log2 qi ⌋ + 1).i =1При a1 > 1 выполнено ⌊log2 a1 ⌋ + 2 ¶ 3 log2 a1 и, как следствие,n‹nXXc(⌊log2 a1 ⌋ + 1)(⌊log2 qi ⌋ + 2) ¶ 3c(log2 a1 ) n +log2 qi =i =1i =1= 3c(log2 a1 )(n + log2 (q1 q2 ...qn )) ¶ 3c(log2 a1 )(n + log2 a0 ).Как мы знаем, n ¶ 2 log2 a1 + 1; при a1 > 1, очевидно, можем написать n ¶ 3 log2 a1 . Это дает нам оценку сверху3c(log2 a1 )(3 log2 a1 + log2 a0 )для числа битовых операций при a1 > 1. Учитывая, что a0 ¾ a1 , мыполучаем отсюда следующее.Количество битовых операций, затрачиваемых при примененииалгоритма Евклида к a0 , a1 , допускает оценкуO(log a0 log a1 )(.)и оценки O(log2 a0 ), O(m2 ), m = λ(a0 ).Приведенные оценки получены в предположении, что для построения остатков используется наивное деление, имеющее квадратичнуюсложность.

Может ли быть так, что привлечение имеющего меньшуюбитовую сложность алгоритма деления с остатком приведет к существенно меньшим битовым затратам алгоритма Евклида? Ответ отрицательный: нетрудно, например, показать, что если a0 берется в качестве размера входа, то для битовой сложности алгоритма Евклидавыполняется оценка Ω(log2 a0 ).В самом деле, в примере . было показано, что для каждого a0 можно подобрать меньшее его a1 такое, что для числа деленийс остатком выполняется неравенство (.).

Если обозначить это число делений через n, то будем иметь n = Ω(log a0 ), при этомλ(a0 ), λ(a1 ), ..., λ(an )Глава . Битовая сложностьявляется невозрастающей конечной последовательностью натуральных чисел, и в силу предложения . никакое значение не встречаетсяв ней более двух раз. Так как деление с остатком ai−1 на ai требуетне менее λ(ai ) битовых операций, то общее число битовых операций не jможетkбыть меньше, чем 1 + 1 + 2 + 2 + ... + k + k = k(k + 1)n+1и n = Ω(log a0 ).

Следовательно, общее число битовыхпри k =2операций есть Ω(log2 a0 ).Вместе с ранее установленной оценкой O(log2 a0 ) это дает оценкуΘ(log2 a0 ). Теорема . из §  приводит нас к оценке Θ(m2 ) для битовой сложности алгоритма Евклида при избрании битовой длины mчисла a0 в качестве размера входа. Итак:Если алгоритм Евклида основывается на некотором алгоритме деления с остатком, битовые затраты которого применительно к делимому v и делителю w допускают верхнюю оценку O(log v log w),то при рассмотрении большего входного числа a0 в качестве размера входа битовая сложность алгоритма Евклида допускает оценкуΘ(log2 a0 ). При рассмотрении m = λ(a0 ) в качестве размера входа имеем оценку Θ(m2 ).Оказывается, что полученные оценки сохраняют силу и при рассмотрении расширенного алгоритма Евклида (пример .) — обстоятельство, имеющее большое значение для модулярной арифметики(§ ).Предложение ..

Пусть расширенный алгоритм Евклида основывается на некоторых алгоритмах деления с остатком и умножения, битовые затраты каждого из которых применительно к целымv и w допускают верхнюю оценку O(log v log w). Тогда, при рассмотрении большего входного числа a0 в качестве размера входа, битовая сложность расширенного алгоритма Евклида допускает оценкуΘ(log2 a0 ), а при рассмотрении битовой длины m большего числа a0в качестве размера входа — оценку Θ(m2 ).Доказательство.

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

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