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

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

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

Имеем для достаточно больших m1 , m2 и некоторойположительной константы cT∗∗CNM(a, b) ¶ TNM(m1 , m2 ) ¶ cm1 m2 ¶ 4c log2 a log2 b.TМы можем написать CNM(a, b) = O(log a log b), считая, что выражениепод знаком O рассматривается как функция двух переменных a, b,при этом a, b → ∞; считаем также, что логарифмы имеют общее основание (подобные предположения будут подразумеваться и в дальнейшем). Остается заметить, что битовая временная сложность прииспользовании самих a, b в качестве параметров размера входа совпадает с битовыми временными затратами.

Это позволяет получить∗∗из оценки TNM(m1 , m2 ) = O(m1 m2 ) оценку TNM (a, b) = O(log a log b) для§ . Наивная арифметика: умножениевременной битовой сложности при использовании двух параметровразмера входа a, b. Итак:При использовании самих положительных целых a, b в качествепараметров размера входа сложность наивного умножения a на b почислу битовых операций допускает оценку O(log a log b).Выше наивное умножение (умножение «столбиком») понималосьтак, что если какая-то цифра числа b равна нулю, то, несмотря наэто, построение соответствующих ni и si требует не менее m1 битовых операций. При таком взгляде сложность будет величинойΘ(log a log b).

Но можно считать, что в рассматриваемом случае битовые затраты на получение si не зависят от a и ограничены константой. Тогда оценка Ω(log a log b) места не имеет: если a = 2k1 , b = 2k2 ,где k1 , k2 — положительные целые, то битовые затраты будут ограничены линейной функцией от k1 , k2 .Пример ..

Покажем, что битовая временная сложность алгоритма вычисления n! с помощью пошаговых наивных умножений2 · 3, (2 · 3) · 4, ..., (2 · 3...(n − 1)) · nпри использовании n в качестве размера входа допускает верхнююоценку O((n log n)2 ). В силу предложения . и неравенства (.)рассматриваемая сложность не превосходит cf (n), где c — некотораяположительная константа, а значение f (n) равноlog2 2 log2 3 + log2 (2 · 3) log2 4 + ... + log2 (2 · 3...(n − 1)) log2 n.Имеемf (n) ¶ log2 (2 · 3...(n − 1))(log2 2 + log2 3 + ... + log2 n) ¶ log22 (n!).Одним из следствий формулы Стирлинга является оценка log2 (n!) == O(n log n), откуда log22 (n!) = O((n log n)2 ), и f (n) = O((n log n)2 ).Пример ..

Мы упоминали о том, что для алгоритма, входомкоторого является несколько целых чисел, можно в некоторых случаях определять размер входа как суммарную битовую длину всех этихчисел. Предположим, что имеется несколько целых чисел 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 .

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

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