С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 7
Текст из файла (страница 7)
Этодаёт возможность написать оценку через Θ .( )*Что касается оценки TND(m) = O m 2 , то она следует из того, что m 2 ≥ ma mb ≥ (ma − mb + 1)mb .Для доказательства нижней оценки, рассмотрим a = 2m − 1 и b = 2⎣ 2 ⎦ , которые являютсясамыми неудобными для алгоритма. Это позволяет написать нижнюю оценку, что завершает*доказательство оценки TND( m) = Θ m 2 .m( )Когда a и b рассматриваются в качестве размера входа, то битовая сложность допускаетоценку O((log a − log b + a )log b ) ⇒ O (log a log b ) .
Если брать только a, то O(log 2 a ) .32Пример. Пусть на входе имеется n и k ≥ 2 . Требуется перевести n из двоичной системысчисления к системе с основанием k. Покажем, что битовая сложность такогоалгоритма допускает оценку O(log 2 n ) .n в k-ичной записи формируется из остатков от деления чисел q0 , ... , qt , t = ⎣log k n ⎦ + 1⎢q ⎥на k, где q0 = n , qi = ⎢ i −1 ⎥ , i = 1, ... , t . Все qi ≤ n , и общие затраты на всех шагах⎣ k ⎦допускают оценку O(log n log k log k n) , log 2 k log k n = log 2 n ⇒ O (log 2 n ) .14243 123затраты на числоодном шаге шагов ( t )Интересно, что если известен некоторый алгоритм умножения со сложностью TM (m) , то понему можно построить алгоритм деления со сложностью не хуже, чем O(TM (m) ) .Исследуем алгоритм Евклида на битовую сложность.
На входе два числа: a0 ≥ a1 > 0 . Ранеебыло сказано, что величина a0 не сильно влияет на алгебраическую сложность, т.к. послепервого же деления с остатком получим число, меньшее a1 . Но в случае битовой сложностиэто не так. Если в качестве размера входа взять a1 , то сложность будет бесконечной. Чтобыполучить информативную оценку битов можно в качестве размера входа взять a0 илиm = ν (a0 ) . Возьмём m , тогда можно показать, что для битовой сложности алгоритма( )Евклида имеет место оценка O m 2 . Доказательство этого факта не очень сложное: очевидно,что затраты алгоритма не превзойдут величиныnc ⋅ ∑ (ν (ai −1 ) − ν (ai ) + 1)ν (ai ) .i =1Здесь под знаком суммы написана битовая сложность деления ai −1 на ai , причём числошагов алгоритма Евклида равно n.
Функция ν (ai ) с ростом i убывает, поэтому мы можемнаписать следующую оценку:nnc ⋅ ∑ (ν (ai −1 ) − ν (ai ) + 1)ν (ai ) ≤ cnν (a0 ) + cν (a0 )∑ (ν (ai −1 ) − ν (ai )){ i =1i =1≥ν ( a1 )дальше эта сумма вычисляется легко:cnν (a0 ) + cν (a0 )(ν (a0 ) − ν (an )) ≤ cν (a0 )(n + ν (a0 )) .Всё хорошо, но в оценку влезло n. Но n — это число шагов алгоритма Евклида и, как былополучено ранее, является величиной логарифмической: n ≤ 2 log 2 a1 + 1 ⇒ n ≤ 2 log 2 a0 + 1 ,( )откуда следует заявленная оценка O m 2 .()Т.к. эта оценка является верхней, то можно перейти к оценке через a0 : O log 2 a0 . Эта оценкаполучена на базе алгоритма «наивного» деления и возникает вопрос: если использоватьболее эффективный алгоритм деления, можно ли уменьшить оценку? Оказывается, что этоне так, и оценка точная. Для доказательства достаточно положить a0 = Fn ; a1 = Fn −1 , изатраты алгоритма будут примерно равны log 22 a0 , т.к.
для чисел Фибоначчи каким бы не былалгоритм деления, он будет эквивалентен вычитанию.Более того, можно доказать теорему о нижней границе класса алгоритмов Евклида(отличающихся алгоритмом деления) и показать, что она равна log 22 a0 .33Модулярная арифметика.Все вычисления производятся по модулю некоторого числа.Определение. Число a сравнимо с b по модулю k, если число k делит разность (a − b ) .Обозначение: a ≡ b(mod k ) .Утверждение.(i)Отношение сравнимости по модулю k является отношением эквивалентности.(ii) Если a1 ≡ b1 (mod k ) , a2 ≡ b2 (mod k ) , тоa1 + a2 ≡ b1 + b2 (mod k ) , a1 − a2 ≡ b1 − b2 (mod k ) , a1a2 ≡ b1b2 (mod k ) .(iii) Каждое число a сравнимо по модулю k с одним и только одним числом измножества {0, 1, ... , k − 1} .Отношение эквивалентности разбивает множество целых чисел на непересекающиесяклассы, причём количество этих классов равно k. Возьмём по одному представителю изкаждого класса: {a0 , a1 , ...
, ak −1} — полная система вычетов по модулю k. Система⎧⎢ k ⎥⎢ k ⎥⎫I = {0, 1, ... , k − 1} — каноническая система вычетов. S = ⎨⎢− ⎥, ... , − 1, 0, 1, ... , ⎢ ⎥ ⎬ —⎣ 2 ⎦⎭⎩⎣ 2 ⎦симметричная система вычетов. В курсе линейной алгебры доказывалось, что Z k являетсякольцом вычетов по модулю k. При этом вычеты называются изображениями. При сложениискладываем изображения, если остаёмся в рамках канонической системы, то всё в порядке,если получаем число ≥ k , то вычитаем k.
Противоположный a элемент определяется какk − a . Поэтому для битовых затрат операций сложения и вычитания имеем оценку O(m) ,где m = ν (k ) .Если для умножения используем алгоритм «наивное» умножения, то затраты допускаютоценку O m 2 .( )Если k — простое, то Z k является полем, если k не является простым, то Z k — это кольцо сделителями нуля.Сосредоточимся на случае k = p — простое число. Покажем, откуда следует существованиеобратного элемента. Рассмотрим каноническую систему вычетов: {0, 1, ...
, p − 1} . Израсширенного алгоритма Евклида следует, что найдутся такие целые s и t, что будет верноsp + ta = 1 ⇔ ta ≡ 1(mod p) . Следовательно, t будет обратным к a. Но t является целым и,возможно, не входит в систему. Было показано, что t < p , и t может быть отрицательным.Поэтому, если t ≥ 0 , то всё в порядке и t входит в рассматриваемую систему вычетов.
Еслиt < 0 , то прибавим p и попадём в рамки системы (ещё не более одной операции). Затраты накаждом шаге расширенного алгоритма Евклида для перехода от si −1 к si и от ti −1 к tiсравнимы с затратами на деление с остатком. Но расширенный алгоритм Евклида позволяетвычислять только t и не тратить операции на вычисление s. Но для O log 2 p это не имеетзначения.()Пример. a = 5 , p = 132 ⋅ 13 + (−5) ⋅ 5 = 1 ⇒ для числа 5 обратным будет (−5) ⇒ добавим 13 и получим(−5) + 13 = 8 и имеет место сравнение 8 ⋅ 5 ≡ 1(mod 13) .34Как следует из расширенного алгоритма Евклида, обращать можно не только по простомумодулю, лишь бы a и p были взаимно простые.Теорема (малая теорема Ферма).
Пусть p — простое, u — целое, u ≠ 0 ⇒ u p −1 ≡ 1(mod p) ,при условии, что p не делит u.Условие p — простое является существенным: Например, u = 5 , p = 6 ⇒ 55 ≡/ 1(mod 6) . Такчто расширенный алгоритм Евклида в этом плане лучше.Проблемой является распознавание простоты числа такое, чтоб его сложность былаполиноминально ограниченной: O m d , m = ν (n) или, что то же самое, O(log d n ) . Можнопопробовать зацепиться за малую теорему Ферма: u p ≡ u (mod p) ⇒ p — простое. Т.е. можнодля возведения в степень воспользоваться бинарным алгоритмом возведения в степень, нодля сокращения затрат брать результат по модулю.
Далее проверить условия теоремы и датьответ. Но такой алгоритм, вообще говоря, неверный, т.к. существуют составные числаКармайкла (бесконечно много), которые не ловятся таким алгоритмом.( )Тем не менее, в 2002 году три индийских математика — Агравал, Кайал и Саксена —разработали алгоритм определения простоты числа с полиномиальной сложностью. Этоталгоритм базируется на следующем утверждении:Утверждение.
Пусть u, n ∈ N , u ⊥ n (взаимно простые). Тогда n является простым, если итолько если (x − u ) ≡ x n − u (mod n) .nДоказательство. Необходимость. Пусть n — простое и, для определённости, нечётное (дляn = 2 проверяется непосредственно). Сравним коэффициенты при степенях x k для 1 < k < n .В правой части очевидно все коэффициенты равны нулю, а в правой из формулы биномаНьютона получаем (−1) k Cnk a n − k . Т.к. для числа сочетаний верно Cnk ≡ 0(mod n) (см. задачу42), то получаем, что (−1) k Cnk a n−k ≡ 0(mod n) , т.е. коэффициенты в левой и правой частисравнимы с нулём по модулю n. Для k = n доказывать нечего, проверим свободный член:надо показать, что (−u ) n ≡ −u (mod n) , но это следует непосредственно из малой теоремыФерма.Достаточность докажем от противного. Пусть n — составное, тогда найдётся такое q,которое будет являться делителем n.
Рассмотрим ещё k такое, что q k ещё делит n, а q k +1 уженет. Рассмотрим число сочетаний из n по q:Cnq =n[(n − 1) ⋅ ... ⋅ (n − q + 1)]q!Ни один из множителей в квадратных скобках не может делиться на q. В итоге послесокращения должно получиться целое число, которое на q k уже не делится (т.к. одно q иззнаменателя сократится с n). q k ⊥ u n − q , и коэффициент в правой части (−1) n − q u n − qCnq x q несравним с нулём по модулю n, что противоречит утверждению.
Полученное противоречиезавершает доказательство.Просто построить алгоритм определения простоты числа на основе доказанногоутверждения нельзя, но использовать его как основу вместо малой теоремы Ферма вполнереально.Итак, получаем следующий способ определения простоты числа: возьмём u = 1 , раскроемскобки и посчитаем остаток от деления на n. Но после раскрытия скобок получим n + 1слагаемое, и нужно будет поработать со всеми ими. Откуда для сложности алгоритма будетверна оценка Ω(n ) , а n ≈ 2m и всё хорошо, но сложность экспоненциальная.35()Посмотрим, что предлагают авторы. Рассмотрим сравнение: (x − u ) ≡ x n − u mod x r − 1, n ,nкоторое означает следующее:делятся на n.(x − u )n()− x n + u = Q( x) x r − 1 + S ( x) и все коэффициентыЧтобы двигаться к полиномиальности, нужно чтобы r было маленьким.
Возводить в степеньнадо бинарным алгоритмом возведения в степень, каждый раз беря результат по модулю.Во-первых, r берётся не «с потолка», а совершенно конкретным, допуская оценку r = O(m6 ) .Во-вторых, u тоже не является произвольным. Авторы показывают, что достаточнопроверить сравнительно небольшой набор, допускающий оценку O m r ~ m 4 .
Тогда, еслииспользовать эти r и u, то по необходимому и достаточному условию можно распознатьпростоту числа, и сложность будет полиномиальной.(36)Об одном классе рекуррентных соотношений («разделяй ивластвуй»)Мы будем рассматривать рекурсивные алгоритмы. Рекурсивные соотношения дляисследования сложности таких алгоритмов являются эффективным методом. Основой будутлинейные рекурренции с постоянными коэффициентами и, возможно, с правыми частями.Для начала рассмотрим «игрушечный» алгоритм построения множества Vn , содержащего всеположительные целые числа, десятичные записи которых таковы, что сумма их цифр равна n.V1 = {1} . Упростим задачу, рассматривая только такие цифры, десятичные записи которыхсостоят только из единиц и двоек: V2 = {11, 2} , V3 = {111, 21, 12} .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
