С.А. Абрамов - Вычислительная сложность алгоритмов, страница 4

Для оценки количествашагов алгоритма Евклида, которое совпадает с количеством необходимых делений состатком, хорошо было бы найти такую функцию λ (ai−1 , ai ) , для которой выполнялись быследующие условия:1. λ (ai −1 , ai ) ≥ 0 ;2. C E (ai−1 , ai ) ≤ λ (ai−1 , ai ) ;3. на каждом шаге алгоритма Евклида она уменьшается хотя бы на 1.Рассмотрим функцию λ (k , l ) = ν (k ) +ν (l ) − 2 , где ν (x) соответствует битовой длине x .Очевидно, что она удовлетворяет первым двум сформулированным условиям.

Убедимся всправедливости третьего. Справедливо следующееУтверждение. Пусть k, l ∈ N , k > l , r — остаток от деления1. ν (k ) > ν (r ) ;2. λ (k , l ) > λ (l , r ) .Доказательство:1. k = ql + r , q ≥ 1 ⇒ k ≥ l + r > 2r ⇒ ν (k ) > ν (l ) ;17k. Тогдаl2. ν (k ) > ν (r ) ⇒ ν (k ) + ν (l ) − 2 > ν (l ) + ν (r ) − 2 ⇔ λ (k , l ) > λ (l , r ) , что и требовалосьдоказать.C E (a0 , a1 ) ≤ λ (a0 , a1 ) = ν (a0 ) + ν (a1 ) − 2C E (a0 , a1 ) = CE (a1 , a2 ) + 1 ≤ ν (a1 ) + ν (a2 ) − 1 ≤ 2ν (a1 ) − 1123≤ν ( a1 )TE (a1 ) = max C E (a0 , a1 ) ≤ 2ν (a1 ) − 1 = 2 ⎣log 2 a1 ⎦ + 1a0 ≥a1Итак, для сложности алгоритма Евклида была получена оценка: TE (a1 ) = O (log a1 ) . Возникаетвопрос: можем ли мы улучшить эту оценку? Ответ: нет, эта оценка точная.

Длядоказательства точности оценки построим последовательность входов a0(1) , a1(1) , a0( 2) , a1( 2) ,(a)(()) (), a1( 3) , … такую, что для неё будет выполняться C E (a0( n ) , a1( n ) ) = Ω log a1( n ) при n → ∞ . Длянаших целей хорошо подойдут числа Фибоначчи: F0 = 0 , F1 = 1 , Fn+2 = Fn+1 + Fn , т.е.последовательность 0, 1, 1, 2, 3, 5, 8, … Применяя алгоритм Евклида к паре (Fn+1 , Fn )получим ровно n делений: C E (Fn+1 , Fn ) = n .

Используем формулу Бене:( 3)0Fn =()1 n1+ 5φ − (− φ )−n , где φ == 1,61803... («золотое сечение»).25Откуда получаем, что φ n = 5 Fn (1 + o(1) ) при n → ∞ ⇒ n = logφ Fn + O(1) . Тогда для затраталгоритма получаем: C E ( Fn+1 , Fn ) = n = logφ Fn + O(1) = Ω(log Fn ) . Следовательно, оценкаTE (a1 ) = O (log a1 ) точна. Более того, можно показать, что TE (a1 ) = Θ(log a1 ) . Для этого1докажем, что TE (a1 ) > logφ a1 + γ .4⎡FF ⎤Рассмотрим систему вложенных сегментов Φ1 ⊃ Φ 2 ⊃ Φ 3 ⊃ ... , где Φ n = ⎢ 2 n , 2 n+1 ⎥ .⎣ F2 n−1 F2 n ⎦Φ1Φ2...1F2F12F4F3φF5F4F3F2Для чисел Фибоначчи справедливо равенство:Fn2 − Fn−1Fn+1 = (−1) n , n = 1,2,...которое легко устанавливается по индукции (см.

задачу 24). Используя это равенство, длядлины сегмента Φ n получаем выражение:Φn =F2 n+1 F2 nF F − F22n1−= 2 n+1 2 n−1=F2 n F2 n−1F2 n F2 n−1F2 n F2 n−11811≤ Φn =, а дляa1F2 n F2 n−11=⇔ a1 < F2 N +1F2 N + 2 .F2 N +1 F2 N + 2Так как Φ n → 0 при n → ∞ , a1 > 1 ⇒ ∃N : ∀n ≤ N выполняется1> Φ N +1a1N + 1 неравенство уже не выполняется, т.е.Используем формулу Бене и получим:()()1 2 N +21 2 N +1φ− (−φ ) −2 N −1 ⋅φ− (−φ ) −2 N −2 < cφ 4 N55a1 < F2 N +1 F2 N +2 =1logφ a1 − logφ c , что доказывает оценку TE (a1 ) = Θ(log a1 ) .

Для сложности в среднем412 ln 2ln a1 + O(1) .можно получить оценку TE (a1 ) =2⇒N>πРасширенный алгоритм Евклида (EE).Можно показать, что ∃s, t ∈ Z : sa0 + ta1 = НОД(a0 , a1 ) . В частности, если a0 и a1 взаимнопростые, то ∃s, t ∈ Z : sa0 + ta1 = 1 .Пусть в алгоритме Евклида уже найдены a0 , a1 ,..., ai , 1 ≤ i ≤ n − 1 и пусть найдены s0 , t0 ;s1 ,t1 ; … ; si , ti такие, что s0 a0 + t0 a1 = a0 ; s1a0 + t1a1 = a1 ; … ; si−1a0 + ti−1a1 = ai−1 ; si a0 + ti a1 = ai .ai−1 = qi ai + ai+1 ⇒ ai+1 = ai−1 − qi ai = si−1a0 + ti−1a1 − qi ( si a0 + ti a1 ) = ( si−1 − qi si )a0 + (ti−1 − qi ti )a1 , т.е.1424314243si +1ti +1si+1 = si−1 − qi si ; ti+1 = ti−1 − qi ti , при этом s0 = 1 , t0 = 0 , s1 = 0 , t1 = 1 .Пример. a0 = 39; a1 = 15Остатки, получаемые алгоритмом Евклида: 9, 6, 3, 0.s, t: 1,-2; -1,-3; 2,-5; ⇒ 2 ⋅ 39 + (−5) ⋅15 = 3 = НОД(39,15) .Алгоритм Евклида, в котором дополнительно определяются числа ti , si буден называтьрасширенным алгоритмом Евклида (EE).

Не трудно видеть, что для его сложностисправедлива оценка: ё TEE (a1 ) < 6 log 2 a1 + 3 , т.е. всё утроилось.Можно также найти числа sn+1 , tn+1 : sn+1a0 + tn+1a1 = 0 (для примера, рассмотренного выше,sn+1 = s5 = −5; t5 = 13 ).Для чисел si , ti можно доказать следующий факт: s1 < s2 < ... < sn+1 , t1 < t2 < ... < t n+1 .Кроме того, sn +1 =a1a0, t n+1 =, тогда sk < a1 , tk < a0 , k = 1,2,..., n .НОД(a0 , a1 )НОД(a0 , a1 )Бинарный поиск (BS = binary search).Есть массив x1 ,..., xn , элементы которого упорядочены по возрастанию. И есть ещё одинэлемент y, для которого нужно найти место в этом массиве такое, что после вставкиэлемента y полученный массив был упорядоченным.

Существуют следующие варианты длявставки y:y ≤ x1 ,1x1 < y ≤ x2 ,2x2 < y ≤ x3 , ... xn−1 < y ≤ xn , xn < yn3n+1Задачей алгоритма является выдача числа от 1 до n + 1 , соответствующего вариантуправильного расположения y.19На псевдокоде алгоритм выглядит следующим образом:p:=1; q:=n-1;while p<q do⎢ p + q⎥;⎣ 2 ⎥⎦r:= ⎢odif xr<y then p:=r+1 else q:=r fiНе трудно видеть, что каждый шаг алгоритма переводит рассматриваемую задачу для⎢k ⎥⎢k ⎥массива длины k к задаче для массива длинны ⎢ ⎥ или ⎢ ⎥ − 1 . Введём функцию⎣2⎦⎣2⎦λ (k ) = ν (k ) , тогда на каждом шаге алгоритма λ (k ) будет убывать хотя бы на 1.

Если y ≤ x1 ,то λ (n) = ⎣log 2 n ⎦ + 1 = TBS (n) = ⎡log 2 (n + 1)⎤ .Сортировка бинарными вставками.Рассмотрим алгоритм сортировки массива, основанный на алгоритме бинарного поиска.Алгоритм заключается в следующем: создается новый массив, который формируется изэлементов исходного, каждый новый элемент занимает место, определяемое алгоритмомбинарного поиска. Тем сам на i-м шаге уже имеется упорядоченный массив из i − 1 элемента,в который вставляется i-й элемент исходного массива.n −1nl =0k =1nДля сложности в худшем случае имеем: TB (n) = ∑ ⎡log 2 (l + 1)⎤ = ∑ ⎡log 2 k ⎤ = ∑ log 2 n + O(1) .k =1n −nИз курса математического анализа известна формула Стирлинга: n!= n en∑ logk =122πn (1 + o(1) ) ⇒n = log 2 n!= n log 2 n + O(n) ⇒ TB (n) = n log 2 n + O (n) .Сортировка фон Неймана (vN).Имеется массив x1 ,..., xn , который требуется упорядочить.

Пусть на каком-то шаге алгоритмамассив разбивается на некоторое число упорядоченных сегментов. Тогда на следующемшаге сегменты объединяются парами и элементы внутри новых сегментов упорядочиваются.Далее опять происходит слияние сегментов по два и т.д. Причём для слияния сегментовиспользуется вспомогательный массив такой же длины, что и исходный. Схематичнодействие алгоритма можно изобразить следующим образом:⇒⇒При слиянии сегментов используется информация о том, что каждый из сливаемыхсегментов сам по себе уже упорядочен, поэтому для слияния и одновременногоупорядочивания двух сегментов длины k необходимо менее 2k операций сравнения, т.к.новый сегмент длины 2k формируется в новом массиве (новый сегмент формируетсяпоэлементно из меньшего из наименьших нерассмотренных элементов исходных сегментов).На первом шаге исходный массив делится на сегменты длины 2 (за исключением, бытьможет, одного сегмента длины 1 в случае, если исходный массив имеет нечётное количествоэлементов), на втором шаге — длины 4 (если не было парного какому-то сегменту, то ещё неболее одного сегмента длины 1, 2 или 3) и т.д.

Таким образом, число этапов (перебросок) всортировке фон Неймана будет равно ⎡log 2 n⎤ . Т.к. число присваиваний на каждом этапе20равно n, то общее число присваиваний, необходимых алгоритму, будет равно n ⎡log 2 n ⎤ . Длячисла сравнений получаем следующую оценку: TvN (n) < n ⎡log 2 n⎤ .Завершимость алгоритмов.Рассмотрим следующий пример.Пример. (блуждание частицы по целым числам) В начале координат имеется частица,которая может двигаться на единицу влево или вправо с одинаковой вероятностью.Оказывается, что ∀m ∈ Z частица рано или поздно попадёт в точку m , причём свероятностью 1. Но среднее необходимое для этого время (даже если m = 1 ) равно ∞ .Алгоритм кратных карт.Имеется колода карточек, на каждой из которых с одной стороны пишутся вопросы, с другой— ответы.

Все вопросы разной сложности. Обучаемый перебирая по очереди все карточкидолжен отвечать на вопросы, если ответ неверный, то можно посмотреть ответ на обороте.Если обучаемый отвечает на вопрос карточки, то она изымается, если не отвечает, токарточка возвращается в колоду, плюс добавляется еще одна такая же.Рассмотрим стратегию «двоечника», когда обучаемый всегда отвечает неправильно.Пусть все вопросы в колоде имеют кратность > 1 кроме одной.

Если m — суммарнаякратность карт, то вероятность вытащить первый вопрос (вопрос кратности 1) на первом1шаге равна. Вероятность вытащить первый вопрос на i-м шаге равна:mm −1 mm+i−2 1m −1⋅⋅ ... ⋅⋅=m m +1m + i − 1 m + i (m + i − 1)(m + i )Тогда вероятность того, что рано или поздно вытащат первый вопрос, будет равна:P=∞11+ (m − 1)∑mi =1 ( m + i − 1)( m + i )Покажем, что полученный ряд сходится:n1111111→∞=−⇒ Sn = ∑= −⎯n⎯⎯→m m+nm(m + i − 1)(m + i ) m + i − 1 m + ii =1 ( m + i − 1)( m + i )⇒P=11+ (m − 1) = 1mmЧто соответствует тому, что первый вопрос рано или поздно будет вытащен с вероятностью1.

Посмотрим, какое время для этого потребуется:∞T = (m − 1)∑i =1i(m + i − 1)(m + i )Не трудно видеть, что полученный ряд расходится. Это соответствует тому, что длявытаскивания первого вопроса потребуется бесконечное время.Пусть теперь u ≥ 2 карточки имеют кратность 1. Тогда для вытаскивания вопроса скратностью 1 потребуется времени∞T =∑i =1i + u +1(i + m)(i + m + 1)...(i + m + u )Полученный ряд, как не трудно видеть, сходится, а значит, мы увидим вопрос с кратностью1. Далее по индукции легко установить, что пока u ≠ 1 мы увидим все вопросы.21Допустим, что программа содержит какие-то цифры и её нужно исследовать на сложность.Рассмотрим пример.Пример.